It sounds like you've fixed the problem but I'll throw my bit in just because.

Gmail is ruthless when it comes to 'spam' it'll kill anything instantly if it suspects it. I stopped using it because of this, none of my mail was getting through.