Network ID problem

I am using Windows networking (Microsoft Client and NetBEUI). When I change a network ID (computer name) on a PC the new name shows up on the network and the old name is still there. Here it is the next day, all PC’s have been re-booted, and this bogus (the old and now non-existent)computer name still exists on the network. Any experience?