If you're on iOS 5 you'll have to manually edit the icons you want to change. I use iSpirit to get to the theme folder (private/var/stash/themes/your theme/bundles/com.apple.mobileicons.framework/). Once there you'll have to add ~iphone to the end of each icon. For example:
AppIconMask@2x.png now needs to be
AppIconMask@2x~iphone.png Do that for every icon in your framework folder. Once that's finished you'll notice that your phone and mail icon didn't change but just about everything else should have.
For your mail icon open your com.apple.mobilemail folder and capitalize the i in
icon@2x.png so it should be
Icon@2x.png. For your phone icon to change open your com.apple.mobilephone folder. Here you need to add the ~iphone at the end of the icon again. So it should look like this:
icon@2x~iphone.png.
I usually do all this editing while the theme is still loaded on my phone. You won't notice any changes until you unselect the theme and respring then select the theme again and respring. After doing all that all of your icons should be themed. Hope this helps because it took me a while to figure it out and can understand how frustrating it can be.