I'd take the following into account:
Take into account whether or not you "owe your users an explanation". Are there a lot of frequent buyers, that will feel slighted because you didn't explain what happened here? It's sort of a "protect your brand" exercise.
Did you change from expertsexchange into stackoverflow, from audi.com into mercedes.com or maybe from github.com into hubcabsales.com? Those are some vastly different scenarios, and some might need an explanation, while others don't really.
You might need to educate your users about your change in name. If you feel really strongly about dropping that one letter from your name (if for example Pepsi dropped a P and went for Epsi) you might want to communicate it to your audience, over even "celebrate" the new name.
Perhaps you might even discontinue the other URL, or sell it, in which case you'd have to notify your users in advance.
Alternative solution to your issue
Redirect, and show a message saying "Hey, we see you entered -url- but we've moved" on the new site.
That way, you've done your due diligence in helping them get to the new url and educating them about the move, whilst minimizing the negative impact on the user experience.