My email (hosted via Bluehost) is setup to be accessed through gmail with SSL encryption via the standard setup instructions. However, I've noticed strange behavior. If I am sending emails to webservers I know are also using SSL (such as accounts on my other domains) then I do not receive gmail's "red padlock" indicator of lack of encryption. Also, if I send emails to gmail users there is no red padlock. But, if I receive emails from gmail users, there is a red packlock saying that the message is not encrypted. Various sources report that gmail's messages are indeed encrypted.
What could be causing this issue? Is there something wrong with Bluehost's certificates?