Why did this get bounced back?

There should be more information in your error message that you haven't posted here...generally the descriptive parts of the errors have a "5" code (i.e: 5.7.1)

Can you post that information?

Make sure your mx records are pointing to the correct server.  They may need to be updated since you changed your domain.

There are a number of tools online that will tell you what your mx records are.  Try looking up your domain on www.mxtoolbox.com/supertool.aspx

That is literally all of the bounce back my clients are receiving. There is a code listed above at 5.2.3... Could that be what you are looking for?

mviau - I didnt change my domain, I just changed it on the posting so I didnt have my domain out there for public viewing.

A 5.2.3 error is the message is too large:
http://www.microsoft.com/technet/prodtechnol/exchange/guides/ExMgmtGuide/fb7830cf-23c6-48a6-8759-526b7854ae39.mspx?mfr=true
It may be their ISP or whoever they send their mail to first that has a limit set that they are busting.

http://support.microsoft.com/kb/284204

Numeric Code: 5.2.3

Possible Cause: The message is too large for the local quota. For example, a remote Exchange user may have delivery restrictions set with max incoming message size.

Troubleshooting: Resend the message without attachments, or set the server side limit or the client side limit to permit a larger message size.

This is not necessarily a clear-cut situation of the same answer being provided with the second correct answer being accepted.
Sufianmehmood's comment does not advise what size limits can be set, how to check the size limits nor where to check them and depending on the knowledge of Agentkolb, he/she may have easily missed the least obvious settings and still not have resolved the issue, based on Sufianmehmood's comment http:#a27639854.
The comment that I posted which was accepted (http:#a27639866) with the relevant link, advises ALL the various places that restrictions can be set and where to check / set them, thus offers much more overall information than a quick comment, neither of us knowing what knowledge Agentkolb has with Exchange 2003.
Size limits can be set in the following places:

• Global settings
• System Policy
• Individual mailbox
• Individual message limit
• Distribution list
• Public folder
• Connector Virtual SMTP Server

We don't currently know which of the relevant locations was the solution for the problem and without Agentkolb's input, we won't ever know, but it could be agued that this is similar to removing the lid of a jar, Sufianmehmood loosened it and I actually removed the lid, but it could be questioned whether Sufianmehmood had loosened it in the first place.
Bearing in mind that Sufianmehmood is relatively new to EE and that I am not, I feel that it would be worthwhile mentioning that the answers that tend to get accepted by the question askers are usually the ones that offer greater information and suitable links to relevant detail than the ones that are just a short comment.  I learned this in my early days of EE (but have been known to forget from time to time ; ) ).
Should Modus_Operandi feel that a points-split is warranted, I will not object, but I will leave that up to modus_operandi to determine and also the percentage split, should a split be deemed necessary.

as far as loosening of the lid is conecerned "alanhardisty" did it earlier, i tried to explain it in a little bit more detail being msexchange specific.....