The culprit is the "Type" of "Common Programs" and "Common Startup" at HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\User Shell Folders.
They were supposed to be "REG_EXPAND_SZ" and not REG_SZ just like the other entries. So I had to delete those two and replace them with the accurate types before restarting and running the HP software again
It took me long hours to figure that out!!!