How is the share/shares? referenced on the client machines? (eg, drive mapping via logon scripts, drive mapping via windows made permanent, use of the UNC name \\server\share - in a shortcut?...). What share(s) are we talking about (data store...)
If its script - fairly obvious, change the script. If mapped via windows, could add a script to map to new location (old one will obviously fail anyway). If its shortcut to the actual name, where does the shortcut live (on each individual desktop, in roaming profile etc). You could edit one and copy to all others?
There may be a clever way of doing this (obviously not in my head currently!) - but even if there is, I think it will depend on exactly where all your references are.