Ok, so it turns out that it didn't like the 9.3.1 ArcGIS Server Map Cache but now I have another problem.
I installed 10 on a dev box and created a new map service based on an mxd that had its extent changed to custom extent. I created a map cache (exploded) and then copied it to location that ArcGIS Mobile Project Center could access it. I added it in as a base map layer and it came up on the map. I saved the project as a wmpk. However, when I opened the wmpk the screen was blank and when I try to zoom in to an area I get the following error (see attachment).
It seems to not be able to access the bottom left extent I guess? Anybody got any suggestions?
Thanks!
Cameron