Hmmm strange that you can package it, but not turn it into a GP Service.
It should be going through the same code paths to do both of those actions.
Since it says it failed on consolidation, it sounds as if you are not using a datastore (you're copying data out of SDE, putting into an fGDB and moving that to Server - well thats what happens when you dont use data store).
Could you register your SDE connection with the Server and try to publish again. Does that succeed?
If not, you said you have been able to successfully package it. Could you send me the package and I'd try your workflow here?
khibma[@]esri.com