So, I'm thinking this error is because I'm trying to input a feature class and some kind of validation is going on under the hood. It's not entirely clear if this behaviour is supported though.
At 10.0, feature classes are clearly not supported (see Input data types section here), but at 10.3, it is less clear. It looks like a feature class is a transportable dataset and it should work (and the tool published without error, which would also suggest that it is possible). The thing is, I have set parameter type as Feature Class in ArcGIS Desktop, yet the REST services directory says the parameter is a GPFeatureRecordSetLayer.
So, can I pass feature classes as parameters or not?