Need more info to work with other than 'it's not working' 'I can't connect to it' the 'can't resolve hostname' error is useful, but you need to follow up on it with basic troubleshooting steps..
Did you log into the mail server and test DNS resolution ?
dig mail.relayserver.com
Did you verify the correct dns servers are in /etc/resolv.conf ?
Did you check the posfix configuration for errors ?
postfix check
Last time I had a DNS issue on my mail server, postfix check revealed to me that the DNS servers listed in the chroot for postfix, did not match the correct working DNS server entries in /etc/resolv.conf
Have you run through the basic diagnostics ?
http://www.postfix-book.com/debugging.html
This was working previously, correct ? What if anything on the mail server or network was changed before it quit working ?