I couldn't embed thumbnail sizes on my new WordPress install on my new Ubuntu server; I could only embed the original size (which was 3072×2048). The options to embed other sizes were just grayed out. It turns out that the default LAMP install doesn't include php-gd, the graphics library that creates thumbnails. Well… I guess that's easy enough to fix:
apt-get install php5-gd