1. Try this in a new user account.
2. The task bar repair tool noted at http://www.majorgeeks.com/files/details/taskbar_repair_tool_plus.html
For the life of me I have researched and researched this.
Basically, I can't pin any items to the taskbar. Nor can I add the desktop link to the taskbar. I think this also is tied into the recently used programs in the start menu as none are displayed.
I've tried editing the registry, I have also made sure the lock taskbar isn't checked. I am out of ideas.