Ubuntu – Bash History not containing all history and blank after reboot, how to resolve

I've recently upgraded from 13.04 to 13.10 and realized my terminal bash history is not surviving reboots.

cat ~/.bash_history gave me a permissions denied error.

I, possibly unnecessarily or wrongly, issued a chmod 777 ~/.bash_history to see if that would help…and although I could then cat and read some contents it contained not much of anything as far as history.

I also tried sudo rm ~/.bash_history after reading bash history not being preserved

Strangely, after doing that, I typed a few test commands, ls, ls -lah … and upon pressing the up arrow to go back through history it contained those two commands as well as the odd history from some far off time in the past but very few results and not the hundreds of commands I typed earlier in the day.

Is there a new place bash history is stored? How can removing ~/.bash_history not get rid of the commands that are somehow lingering? I am not certain, but I believe my root bash history is acting normal. My user bash history is what's causing me trouble. Any help and guidance in tracking down and solving this problem is appreciated.