Entity Reference create problem with REST server using Services
I found the solution!
The required data structure depends on the input widget, since Services uses the form submit handlers (which may be a major design flaw).
For "Autocomplete/Tagging" the label (id) thingy is necessary. But if you switch to checkboxes it reads "field_reference": { 1:1, 2:2,  ... ,nid:nid} and for select box "field_reference": [1,2,3 ... nid].

The REST-API depends on the widgets the frontend uses ... but at least it works. I guess its upside is that REST-posts are validated just as normal form inputs are. I'll also have a look at the approach implemented http://drupal.org/project/restws