I would look around to try and find out what was using it, but "netstat -a" doesn't help much, it just says its taken by a local device on the machine, although it wasn't just port 3000, it's the entire range of 3000 to 3030 were "in use". Some days it would work, some days it would fail, from what I could tell it was completely random whether I would be able to start up the server. After senses of humours were lost to the pixies I finally worked it out, and it comes down to a little green icon with two arrows...
It's ActiveSync, and you'll have this program running if you have a PocketPC phone and if the phone is connected, say goodbye to those port numbers. It steals 3000-3030 straight away when you plug it in. Some solutions I have found are to unplug my phone, start Mongrel, then plug the phone back in. Although again, this working is random and highly frustrating. Currently I have resorted to unplugging my phone when I am developing in rails and plug it back in when I'm done. I actually figured this out sometime last year, but saw someone come into #rubyonrails having the same problem and I thought I should probably share it.