You need to have previously registered the PostGIS table with the Geodatabase in ArcCatalog.
Image from right-click menu in Catalog Tree on table.
Be sure that, when you reach the "Fields" tab during registration, you have your "objectid" field recognized as having "Object ID" type, as the GID field in following image.
Next, you shouldn't use a sequence of your own to populate the objectid values. You should use a ON INSERT trigger that calls a SDE database function named "sde.next_rowid". Please refer to these ArcGIS Help items ArcGIS Help - Editing geodatabase data using SQL.
Perhaps you should get some additional background information, like the one you can get in ESRI presentations (as this for ArcGIS 9.3)
As pointed out by Alex in a comment,
arcpy.env.packageWorkspace
is an expected update in your script if you look at where the GP Service is deployed. The packageWorkspace is the directory itself. When publishing a service that uses SDE data, and you've referenced the SDE database in your datastore, a copy of the connection file (.sde) gets moved into the directory and your script is updated to reference that. This is expected and how its supposed to work.
You're right about "generally" speaking per your link different versions will work together:
According to this link I should however be able to publish form 10.2.2 to 10.1 without too many problems.
I do want to point out times though this wont be true. There have been a few tools which have been enhanced between 10.1 and 10.2.2. These tools can only be publish when each product is at the same version. (this is just a general note, this point wont be your issue).
There have also been some bugs fixed between the versions, mostly related to script update and data paths. Again, generally speaking most should work, but there could be cases that they dont. I dont have enough information about your workflow to say that updating Server to 10.2.2 will solve the problem (so I'm not suggesting that).
Your best test is with ArcMap, to navigate down into the v101 folder and find the .RLT (result) file. Drag that into your map. Open the Results window and under the "shared" node, run that. Thats basically like running the service, but running it locally, not via ArcGIS Server. If that works, its Server having problems connecting to SDE. If it doesn't work, its not resolving the path to your SDE connection file and I'd sort of expect the version differences perhaps messing something up. The easy "test" to prove that would be to hack the script in that directory to point to the connection file explicitly.
Best Answer
The answer for me was to look at http://blogs.esri.com/esri/arcgis/2013/10/10/quick-tips-consuming-feature-services-with-geoprocessing/ and then create Python scripts which directly extract what's needed out of me map services.
Below is an example, which is running off an ArcGIS server on my desktop. It's doing what Select by Attribute would otherwise do. In this case, it's selecting a farm field boundary by name. The field boundary runs as a feature service and users draw the boundaries using the JSAPI Edit Dijit.
I'd hope that ESRI would add some more standard tools which would directly do this sort of thing. Maybe in 10.4, since 10.3 is already out the door this week...