Ah, I had tried changing the Options section email, but not the user one. When I changed the user one, the email came through right away. Change it back, and nothing. Must be Gmail is having a problem with the email notification.
Funny how the email notification uses the user profile, and not to the one you put in Options. If I have multiple users on my blog, do they ALL get an email everytime I have a comment?