I managed to accidentally install GRUB to /dev/sda when setting up my MacBookPro to boot Ubuntu, WinXP and Mac OS X. I knew I shouldn't have, but I wasn't paying attention to the installer when it asked me. In my defence I was also slightly rushed as I wanted to get the installation running before I went to the pub...
Anyway after much hunting and not being able to boot Linux or Windows XP, I finally discovered the solution in this blog post. The author had, like me, managed to ignore all the warnings. Luckily recovery is just a simple case of sticking in the Mac OS X install CD, booting off it and running "fdisk -u /dev/rdisk0" in terminal. This will then restore the Mac OS X MBR to it's proper state.
I did get a warning about not being able to find an MBR file, but it still let me update the MBR and it all seems to be working anyway. As well as fixing Linux and Windows XP booting (which previously would just sit there with a blinking cursor in the top left) it also fixed the slightly annoying issue of rEFIT having a 'Boot Linux from HD' option which I couldn't get rid of.