It's not possible to change the name of a Chef node that already exists. But you can effectively do this by deleting the node on the Chef server and re-creating it, which is not actually as scary as it sounds, here's how.

[Chef server] means do this step on the Chef server (or Hosted Chef), and [node] means do it on your server, the node you're renaming.

1. [Chef server] delete the node
2. [Chef server] delete the client for the node
3. [Node] delete /etc/chef/client.pem
4. [Node] edit /etc/chef/client.rb and add node_name "new-name"
5. [Node] run chef-client
6. [Chef server] edit the newly created node:
   1. set the run list
   2. set the environment
7. [Node] run chef-client

Remember that a Chef node name must match the pattern /^[\-[:alnum:]_:.]+$/.

If you've gone to the trouble of setting a descriptive node name you might find it convenient to use that as the hostname as well. Chef on Rails, my Chef repo for deploying a standard Rails app, has a recipe to do just that.