Was there ever a solution for this? I am having the same issue on a new workstation running Windows 7 64 bit
For those of you running Windows 7: if you have redirected your My Documents folder to a network drive you will not be able to use the basemaps or ArcGIS Online. Windows 7 does not allow you to index a mapped drive and the map packages do use indexing. The only way we have found to get around this is to have your My Documents folder pointing your local hard drive.