Ok, seeing as how I have no clue what is wrong, and after looking into things a little more, I think there is a serious configuration error somehwere.
If I telnet to 25 and ehlo localhost, I immediately get disconnected, both locally and remotely. I found a forum stating telnet can't be used with TLS, so I used the command they gave, and ehlo worked fine. I have, as far as I know, all of the proper ports open with ufw. I'm seeing some stuff in my syslog that looks like ufw rejections, so I'm going to put up some pastebins.
/var/log/mail.log (this is only a portion from this morning, and includes a connection from gmail):
/var/log/syslog (again, from this morning, and where I see some stuff I don't quite get):
Also, for a more specific reference, any non-default configuration was done using this Perfect Server How-TO: