Did you repave it with a fresh Windows install, or is this the default, manufacturer-installed crapfest?

If the latter, I'd put good money on that being your problem. There's some HP-installed crap that's screwing up the taskbar.