This is true, there are programs that house program information here, such as options, preferences or whole profiles.
Your start menu information is also stored here, and as you found out, the task bar.
If there is nothing changing from the program data folder, your information should be able to come back if you overwrite everything in the process.
Try restoring the Program Data folder to an earlier date before you made changes.
1. Right click on Program data folder and click on properties
2. Click on Previous Version tab
3. Select the date when you have made changes in the list
4. Click on Restore button and click on Ok.
If this still doesn't work, you can run your installation CD, and repair windows.