Try this for me - assuming your "recently played" is updating from the software.
Connect your device to your PC. Log in.
Go to "settings," "device," "linking."
If it says "Your device is linked to Zune Tag <whatever>", click "remove link."
Otherwise, check the radio button for "Link my Zune to a Zune Tag"
You can choose whether or not to enable Marketplace purchases, that's not relevant here. (The checkbox below)
Click "Next" at the bottom.
Sign in and hit "confirm."
You should now see "Your Zune is now linked to <tag name>."
Unplug your device, play some music on it.
Then plug your device back in and sync.
Post here whether this worked to upload device plays.
Jessica Zahn, Zune Social Program Manager ~ This posting is provided as-is with no warranties, and confers no rights.