Well, I have re-installed with a Sandisk 2Gb "Cruzer Blade" (A lovely little thing, only £5 and tiny! From 7dayshop in the UK) and it appears to be working perfectly!!
Score -1 for any memory stick from HP, though. I can't confirm if it was due to the 2Gb / 4Gb remark from earlier, but it just would not play nicely.
The 2Gb Cruzer Blade is doing great so far, will update this thread if I run into more problems.