i know its a little late but, i was having the identical problem last friday... but i would get the messages forwarded to the BB (8700c by the way, Cingular) but when i would try to download the attachments (background images) it kept saying i didn't have the proper services... what i did was;
1. logged into the BlackBerry Start Page from the MediaNET home page (on the internet browser on the phone), and DELETED my gmail account from that list...
2. then i deleted the service book for my gmail account on the phone
3. then i logged back into the blackberry start page from my computer (http://www.cingular.com/blackberrystart
4. sent the service books
5. picked up my phone, still no service books so, i went to the Host Routing Table and "registered"
6. shut the phone off, removed battery for 30 seconds to a full minute... replaced battery (phone booted up) turned wireless on again, and BOOM everything was working flawlessly!!!!!!!!! have had no problems since...
removing the battery seems to clear up almost any problem with this phone from what i can see anyway, a typical response to a problem on here is "have you removed the battery and rebooted" i just think thats funny...
maybe that will help someone in the future, i am still new to this whole BB thing, and still don't quite understand the differences between BIS and BES, but i'm searching!!!