Huge Hostname problem

[iLLuSi0nS]

I got listed with the CBS as a potential spammer or a mis configured mail server. the reason is because the hostname of my server was localhost.localdomain and this is a no no in the world of spammers. So i had to change the hostname to be removed from the CBS black list. so i changed it to: mymaindomain.com which should of been server1.mymaindomain.com but it doesnt make a difference. After i changed it, none of my users from other domains that i host can send out mail. 553 sorry, that domain isn't in my list of allowed rcpthosts (#5.7.1)
we can send to each other on the server, but we cant send out to anyone. heres the tricky part, my main domain is the only one the can send mail out fine, to anyone, its ever other domain on my server thats having a problem. Also, i have checked all rcpthosts and all the domains seem to be listed that i have created as an account and domain in plesk. i think it has to do with a dns or ptr problem can someone walk me through a checklist of things to look at to make sure this is working

 

[breun]

Did you change your hostname through Plesk?

 

[Traged1]

Check your files /var/qmail/control/rcpthosts for the domain(s) to see if they are listed in that file?