Home -> Settings -> Applications -> Manage Applications -> Google Apps -> Clear data -> Notifications (top of screen) -> Tap "Your account must be updated" -> Enter new account info -> reboot
worked for me for a G1 i bought off ebay.
http://forum.xda-developers.com/show...e+gmail&page=2