There was a thread about this earlier in the week in one of the forums (maybe the NT 4.0 forum, I can't remember) that had a lot of good suggestions.
We're about to go through the same thing at my place when we replace servers in a couple of months. We have about 75 workstations spread across seven locations, and we have a hodgepodge of names for them, anything from the person's actual name to generic stuff like "Work17."
Here's my tentative plan for how I will attack the renaming:
-- For workstations at the main location that are job specific, I'll probably name them by job title (e.g. PRESIDENT&CEO, VPMARKETING, MISCOORDINATOR).
-- For workstations where the user has someone else with a similar job at another location, I'll probably use a two or three digit code to designate location, followed by a condensed job title (e.g. KPQA, BYSPTECH).
-- For workstations in labs, I'll probably use the location deesignator, followed by the lab title, followed a position number (e.g. BYSP1).
I think this system will work for us, because we don't have a huge network, none of our locations have multiple floors, our offices don't bounce around and we don't have duplicate job titles at any location. If you are faced with that, then you might want to think about using actual office numbers along with a location indicator (e.g. NY754 for a computer in New York, on the seventh floor of the building in office 54). This might be a problem to keep up with, though, if some of those workstations have shared resources (like a printer or a hard drive). Also, if you are going to have multiple servers at the different locations, you want those to be VERY identifiable (e.g. NYPRTSVR for a print server in the New York office).
I guess what I'm saying is that whatever works for you is what you need to use. At the same time, I would HEAVILY document whatever convention you use, so that if you leave, the next guy in your job doesn't have to spend hours trying to figure out which computer is what (like I did).