From the renice(1) manpages:
Users other than the super-user may only alter the priority of processes
they own, and can only monotonically increase their ‘‘nice value’’ within
the range 0 to PRIO_MAX (20).
That's on my Fedora box. I'm surprised what you are describing is working at all on one of your systems.