Tomasz, In http://bugs.debian.org/47467, the bug submitter requests that chfn and chsh allow working on NIS accounts.
As far as I understand, this should *now* be possible because these utilities are PAMified. Could you confirm (I know you're using a NIS setup, so this should be easy to test for you) ?