Today, I learned that if you want to run Disk Clean up in Windows 2008 R2, you have to actually install the feature called Desktop Experience. Launch Server Manager, click on Add Feature, and check Desktop Experience. Disk Cleanup is not installed by default. Who knew?
After a restart, you can access Disk Cleanup via Start > All Programs > Accessories > System Tools.