Alright, I believe I figured it out. For some unknown reason, Qt does NOT make a normal Makefile. It has neither debug or release targets! Those should be defaults! Argh! Loads of extra work to get it working, but I have a working solution to share for others to use.
1) Go to Project->Properties...
2) Check the box "This is a custom Makefile"
3) Click on the "Project's build options..." button
4) Click on the top-most option in the tree on the left. This should be the name of your project!
5) Click on the "Pre/post build steps" tab
6) Paste the following text into the "Pre-build steps" box, being sure to replace "Project.pro" with your project name
$(#qt4)/bin/qmake -project
printf "\\nCONFIG += debug_and_release\\n" >> Project.pro
printf "Debug:DESTDIR = bin/Debug\\nDebug:OBJECTS_DIR = obj/Debug/.obj\\nDebug:MOC_DIR = obj/Debug/.moc\\nDebug:RCC_DIR = obj/Debug/.rcc\\nDebug:UI_DIR = obj/Debug/.ui\\n" >> Project.pro
printf "Release:DESTDIR = bin/Release\\nRelease:OBJECTS_DIR = obj/Release/.obj\\nRelease:MOC_DIR = obj/Release/.moc\\nRelease:RCC_DIR = obj/Release/.rcc\\nRelease:UI_DIR = obj/Release/.ui\\n" >> Project.pro
$(#qt4)/bin/qmake -makefile Project.pro
7) Click on the "Make commands" tab
8) Select "Debug" on the left
9) Modify "Clean target/project" from "$make -f $makefile clean$target" to "$make -f $makefile $target-clean"
10) Select "Release" on the left and apply the changes you made to debug
11) Modify "Clean target/project" from "$make -f $makefile clean$target" to "$make -f $makefile $target-clean"
12) Click the OK button
13) Click on the "Build targets" tab
14) Highlight "Debug", click the "Rename" button, and rename it to "debug"
15) Now rename "Release" to "release"
Everything is fine now, and should build. Note that this is with C::B 13.12 in Wheezy's backports repo and Qt 4.8.2 from the Wheezy repo. The only problem that I see is if you copy the project to a Windows system, you would have to replace the "printf" commands with something else. I chose printf because POSIX echo does not support newline characters.
*EDIT*
Had to disable smileys. They made step 8 a smiley!
Also had to add the steps for modifying the clean commands!