Up until now I have been renaming photos from my digital camera on Windows 7 with a great little application called NameExif. With a handful of clicks I could add the date and time to all my photos from their EXIF data.
In Ubuntu I found that Phatch was a suitable equivalent (although it will do a lot more than just rename files if you want it to).
Phatch is installed as follows:
sudo apt-get install phatch
To run Phatch click Applications, Graphics and then Phatch.
To create a new profile in Phatch I clicked the add button and then selected the Rename preset. Then I just selected the year-month-day-hour-minute-second preset from the File Name drop down menu. Then I simply added <filename> at the end to get the exact configuration that I wanted and saved the profile for future use.