This is something I believe you should have done in the first place. You write that your e-mail setup must not be wrong as you are using Google Apps for your domain- but in the end exactly that might be the problem (wherever it stems from).