I've been wanting to do the same, run Linux off a USB drive for a long time, now. Today with the help of above link, I now have Kubuntu working on my 20gb USB HD. It's great and much faster than booting off the CD.
To test 'persistence', I created an OpenOffice document plus changed the background wallpaper. After rebooting, both the document and the wallpaper were still there. Cool!
Have you tried doing the process all over again? Maybe you missed a step along the way.
I used the HP format utility then I booted off the Kubuntu Live CD and shrunk the FAT partition to 700MB. Then used cfdisk to create a Linux partition on the rest of the USB HD. Finally, ran mke2fs on the second partition to label it 'casper-rw' and make it ext2.
This is the command I used to label and format the Linux partition:
sudo mke2fs -v -L casper-rw /dev/sda2
replace sda2 with your drive designation
Then I followed the rest of the instructions to put Kubuntu on the USB HD.
One last note of caution, maybe everyone knew about this, but the FAT partition was not set active after HP was done formatting it. I had to boot with a DOS floppy, run fdisk and make the FAT partition active.
Hope this helps.