I've been pulling my hair out: I have all the HISTORY variables set correctly, but history never survives to the next session. I thought it must be an Ubuntu 10.04 bug, as only that machine, but couldn't track down anyone reporting the same problem.
The breakthrough came when I stopped typing "history" to view the history, and decided to "cat ~/.bash_history". I got permission denied... and discovered the file was owned by root. Suddenly it all made sense.
(By the way, I've a bunch of blog articles about setting up a new Ubuntu dual boot, RAIDed, encrypted machine; coming soon to an RSS feed near you...)