Just had this very annoying issue with a customer still running Windows 2003, they had changed the default gateway on a server, and then they could browse to a share using the IP Address, no problem with the server name. Naturally the application that needed to access the share needed it to be an IP Address.
Naturally Googling this I found loads of basic explanations of where they could browse by ip and not by the server name, not much use to me, I looked at the lmhosts file, re-installed the networking card but to no avail. Finally I found this post.
Uninstalled KB968389 it worked, reinstalled and it still worked, probably took me more time trying to remember how to apply Windows Updates on a 2003 Server.
Hope fully I have used the right keywords and if you have the issue you find this quick enough. Mind you maybe I should have left it broken and told them to upgrade!
Any questions let me know, till next time.