The subject says it all... I ahve doen the following:
1. Switched to TwentyEleven theme and verified that it is not a theme issue.
2. Tried WP Mail SMTP. Found out Shared Hosting at Hostgator does not allow SMTP, but I set plugin to use PHP mailer and the test message arrives just fine.
3. Disabled WP Mail SMTP and tried mail test as described here (http://butlerblog.com/2012/09/23/testing-the-wp_mail-function/) and mail system seems to be working fine.
4. Disabled all plugins except Gravity Forms had no effect.
Any suggestions would be helpful as I need to resolve this for my client.