If you can access the server from outside your network by IP then there must be something wrong with your MX record. Google for an open relay tester and put your IP in there and see if it is able to connect to the server.
Connection timed out is usually caused by one of two things: a firewall eating the connection (could be on the server itself or the network firewall) or the IP address being wrong and pointing to an unused address where nothing can reject the connection. Note that if you just changed the DNS configuration, depending on how long your DNS records tell everyone to cache the lookup results, they may still be using the old information for a while.
If the IP works from outside of your network and it's been long enough since you set it up that the DNS caches have updated, then figuring out whats wrong with your MX record isn't going to be easy without real information. The only rules for an MX record is that
1) The MX record must contain a hostname (not an IP) and
2) The hostname must have an A record containing its IP (not a CNAME)
Most mailservers identify a completely invalid MX record and bounce with a message saying so.
Your best bet is to use dig MX example.in which should produce something like
;; ANSWER SECTION:
example.in. 6400 IN MX mail.example.in.
Then, dig A mail.example.in should say something like
;; ANSWER SECTION:
mail.example.in. 6400 IN A xxx.xxx.xxx.xxx
The only other thing I can think of is that in the anonymized sample DNS configuration you pasted, the terminating "." is missing from the hostnames, but I don't know if that was because of your search-and-replace or because that paste came from some kind of web-editor which may be hiding those terminating "."s from you. The bounce message you pasted used "mail.example.in." so I suspect it's just hidden.
If the IP doesn't work from outside your network then you'll need to check the server firewall (iptables on Linux) to make sure it's not blocking connections. If you can connect from another machine within your network, then the port is either blocked by your network firewall/router, or your ISP is blocking SMTP.
Also, make sure your Elastic IP is correctly associated with your instance. This looks like a pretty complex operation according to the docs here: http://developer.amazonwebservices.com/connect/entry.jspa?externalID=1346
Best Answer
The email without the mime headers would come across as plain text. The mime headers make the message body gets seen as HTML.