It's true that, for example, dir_fd parameters won't work on Windows.  The solution is to always accept the parameters and throw NotImplementedError on platforms where the functionality isn't available.

Here are my thoughts on the interface for link().  Since the two dir_fd parameters are independent--you might specify none, one, or both--I think the dir_fd=(src,dst) form would be obnoxious.  And polymorphic parameters (accept a string or a tuple of string and fd) are nearly always a bad idea; the % operator on strings is a good example of what can go wrong.  So I think you should stick with the original interface, with independent explicit keyword arguments.

I'd prefer that we did this everywhere it made sense, including adding a follow_symlinks parameter to stat().  But obviously you should prioritize places where we want to get rid of functions that are only in trunk (3.3) so far.

I suppose there's precedent for "followlinks"; it's very old, predating PEP 8.  Personally I'd overlook it if I were doing the implementation and spell the new parameters "follow_symlinks"--or at least I'd try it and see what the community thought.  Anyway, there's no established precedent for "dir_fd" and "remove_dir".  So I'd certainly prefer PEP 8 spellings for those.