I've been getting the same error message when trying to publish a map service from an mxd onto ArcGIS Online.  The mxd only contains a raster dataset from a GDB.  I've tried shortening the path names, as is suggest in the help topic but I still can't get it to work.  Any insight would be greatly appreciated.  
Will