madadman,

I suggest you to rebuild your desktop files and try Beth555's suggestions again.

Or, next to rebuilding your desktop files:

Launch iTunes.
Select Preferences... from Edit menu.
Click General tab.
Clict Set button next to "Use iTunes for Internet Music Playback"