I was inspired by Eric's idea of adding a user-defined setting to the project but I didn't want to run a script every time I built the project.
We know that the iPhone looks for icon files named "Icon.png" by default. It turns out that the "Icon File" setting in the project plist isn't necessary at all if you've named your icon properly. However, if there is no file named "Icon.png" in the project, xCode looks at the value of the "Icon File" setting.
I set a user-defined setting in "Debug" called "Icon_Name" to a non-standard icon name, "DevIcon.png" and "ReleaseIcon.png" for the "Release" config. The "Icon File" setting in the project plist can now be set to ${ICON_NAME} and will take on the value of whatever config file we're using. Now building under two different configurations does use two different icons.
Edit: For multiple icons (high res, small, ipad, etc) I made a slightly different approach. The user-defined setting is now "IconPrepend" which is "Dev" for debug and "Release" for release config. I'm now using "Icon Files" (rather than "Icon File") in the info plist which takes an array of strings. Each string is prepended with ${ICONPREPEND} so that debug configurations look for "DevIcon.png" or "[email protected]" and release configurations look for "ReleaseIcon.png" or "[email protected]".