I submitted a "Hey I'm not an open relay or a spammer!" message to Google the other day, and it appears to have worked.

@gmail.com accepts mail from my server again, hooray!