Postfix can't receive external mail
Solution 1:
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
Solution 2:
You say you have doubts about your MX records. It's not easy to check them without knowing the domain, but try dig MX yourdomain.com
to see what comes up. If that's not the IP of your server, there's your problem.
If you know your MX is correct, the next thing I would try is not just telnetting to port 25, but actually pushing a mail message through using telnet. The SMTP protocol is pretty forgiving of geeks typing in the commands directly. RFC 821 has the details of the protocol; you just send EHLO, then tell it who you're mailing to, what address the message is from, and then DATA to start sending text; close with a . on a line by itself, and it should either accept the message or give you an error message.
I'm betting on the MX records myself, though.