Taskbar JumpLists are not working at all for any program

I just bought a new computer and installed a new copy of Windows 7 Home Premium 64Bit.

I wanted to use the JumpList but nothing happened.
Windows Explorer is pinned to the taskbar (default after installation), both checkboxes in the startmenu/taskbar properties for displaying JumpList items are checked (default after installation).

I tried a lot of things like unchecking the boxes, deleting all files from %AppData%\Microsoft\Windows\Recent\AutomaticDestinations and re-booting (every online help page said this was the cause of faulty JumpList behavior).
Then checking the boxes again and re-booting a 2nd time, but the JumpList still does not let me pin any location from Windows Explorer to the taskbar list.

The AutomaticDestinations and CustomDestinations folders don't really exist in my Recent folder.
Briefly after one re-boot there was a AutomaticDestinations folder, but once I deleted the file in this folder, the folder itself was gone as well.

I also installed this windows update: A Jump List Item is not displayed in Windows 7 or in Windows Server 2008 R2.
Then re-booted and tried the same as above, but still nothing.

I even formatted the hard drive and re-installed Windows 7, but I still have the exact same problem.

I'd appreciate any help, thanks.