I experienced the same problem after receiving a replacement 360. I'm not sure which of these fixed the problem, it may be all of them:
1. Transfered my 360 HDD data to a new hard drive using the MS transfer cable, this is when the problems started
2. Used the DRM Transfer Tool at
Xbox.com | System Use - Transferring Content Licenses to a New Console
3. Deleted the Optional Media Update under Memory->Hard Drive->System Items on the System blade
4. Tried to play a divx file and downloaded the update when prompted.
Everything seems fine now, I guess my issue was caused by the Media Update originally being downloaded to a previous XBox and therefore wasn't licensed for the new one without signing in to Live.
Good Luck.