I create a new install of WordPress and as I was writing up a post or two I noticed the thumbnail options were greyed out and only allowed me to insert my images full sized. The problem was a missing graphics library called GD in PHP. In Ubuntu 8.04 use
sudo apt-get install php5-gd
and restart the Apache server to load the library
Re-upload the image and the option should be available.