Why would they say that? I'm sure you'll get it back.
They didn't just guess your password, you unknowingly gave it to them. That is probably the basis for GD's office fee for dealing with this. As crappy as this sounds, it falls back onto you protecting your passwords.
Here are the likely culprits...
- Weak password.
- Someone you know stole your password in person.
- GoDaddy or email phishing site.
- Trojan on your system. Most commonly picked up off websites (Firefox and Chrome provide a false sense of security), packaged with warez cracks, pirated programs, .rar and .zip files, etc...
- Hacked database somewhere that has your same GD or email password.
- Same password at a rogue domainer's site (forum, blog comments, etc...) that you use for GD or your email.
(Obviously a GD password alone isn't enough, they need account ID too. So this may involve someone you've done business with that also runs a website you go to.)
-

Gmail security breach. They've had pretty much the worse breaches in major email provider history, yet they never make the mainstream news for some reason. I refuse to use this service for anything security sensitive given their poor track record.
(domains stolen in first link)
http://www.makeuseof.com/tag/breaking-gmail-security-flaw-more-domains-get-stollen/
http://www.davidairey.com/google-gmail-security-hijack/
http://www.pcworld.com/article/139758/firefox_exploit_can_hack_gmail.html
http://www.cyber-knowledge.net/blog/2007/01/01/gmail-vulnerable-to-contact-list-hijacking/
The first thing you need to do is change all of your other passwords, ideally right now from a computer that you know is clean. If you don't know for sure, you could download and burn a Linux Live CDR. Ubuntu is popular. The Live versions will run Linux off of the CDR and your RAM without actually installing it on your HDD.
If you don't want to do that, then download a firewall with program permissions. LookNStop is probably the most simple. Install it and reboot. If you have a trojan this will likely prevent it from sending data as long as you block it when it asks.
Then run several free online virus scanners:
http://www.google.com/search?hl=en&safe=off&rlz=1C1GGLS_enUS291US310&q=online+virus+scan&btnG=Search
Also download SuperAntiSpyware and Spybot and do a system scan with those.
Also, it's worthwhile changing your domain's contact info every 60 days so that it resets the time period in which you can't transfer out after changing your contact info. Just something minor. "Ave." to "Avenue" will work. Then if your account is hacked, they at least can't transfer them out of GoDaddy to another registrar before you get things straightened out.