Why can't I use renice to increase a process' nice value?

It's for what I'd call policy reasons. The idea is that normal users can't override the actions of privileged users.

Let's say you're a user on some enormous shared server. You're running monstrous CPU-hogging processes to the detriment of the other users. The sysadmin renices some of your processes because he doesn't like you very much. The OS doesn't remember who did the renice, but it does know that normal users can't reverse the action. In this way, the sysadmin has control over normal users' process priorities.

Since linux 2.6.12, that depends on the value of the RLIMIT_NICE limit (ulimit -e). Which can take values from 0 to 40. That limit is more the limit on the priority of the process (the greater that number, the higher the priority a user can set for a process).

You'll notice the default value is 20 on ubuntu 10.04 and 0 in Debian jessie for instance.

A value of n for that limit means that a process without the CAP_NICE capability can only increase a process priority to up to n, which means decrease niceness down to a niceness of 20 - n. So for a value of 0, that means no non-privileged user can lower the niceness below 20, so no non-privileged user can lower the niceness.

With a value of 20, non-privileged users can decrease the niceness back to 0.

It's up to the administrator to choose whether they allow users to lower their process priority, and to what level by setting the hard limit for that.

As to why an administrator may not want users to lower their process priority, see Flup's answer.