I feel like the world's biggest dummy but do you still need an item for this?

On the Pet (Personal->Pets), find the pet whose name you want to change. There is a little down arrow on top right corner above happiness and hunger, click there, its the third option down.

Or

Personal->Pets->pet you want to change->Pet. On that page is the fourth option down.