OK. So at least it is NOT a permissions thing.

I had this problem as well (only actively noticed when I read about it on this thread), and solved it by deleting the .ash_history files (without really looking at them or their permissions).

It now works OK, but I suspected it might have been something to do with using sudo gainroot perhaps changing the ownership of the user's history to root..

One thing I do now is to always 'exit' instead of just closing xterm. That may also have something to do with the problem, but I haven't investigated it further (WORKSFORME, so to speak).