While the orderby and order parameters work just fine with this: $query = new WP_Query('cat=1,4'); they have no effect what-so-ever with this: $query = new WP_Query('cat=-3');
In addition to that the posts aren't even sorted using the default parameters (date and DESC) when using category exclusion, the posts in category 4 are put last (even though they're newer).
I have tried sending the parameters in an array and also using category__not_in etc. with no difference.