Similar thing happened to me; it turns out someone else had somehow setup an account a couple years ago with my domain (I've owned it since 2000 or so). I was able to get control of the google apps settings for it (they give a couple options, such as adding a DNS entry). However, it was useless because the previous person had set it up in Russian and I couldn't find a way to change it.
I had the same issue and contacted Google Apps support using PIN of another account I already had. I told them the issue and they basically cleared out all the internal Apps data of the previous domain owner. After 48 hours I was able to set it up as new with Apps.
