it sounds like the Notes client only knows how to find the new server by asking the old server. Here are a couple of things you can try:
1) in the client, go to file>preferences>notes ports - use the 'trace' button to trace the path to the new server (using the server's Notes name 'egdomino2/domain') see how the client finds the new server when the old server is on, and again when the old server is off. this should give you a clue to the problem
2) you can create a 'connection document' in the client for the new server - in the 'contact' database under the 'advanced' tab. there you can associate the Notes name of the new server with a dns name or IP address so the client will always know how to get there. this may not be a good solution for your entire environment as it is not easy to create connection documents and distribute them to a large number of client computers, but if you only need this problem solved on a small number of clients it may be helpful.