I've been working for a few days on a module to allow for per-user vocabularies. Needs testing. Here is the README, and the archive is attached below.
The primary goal of the vocabulary per user (VPU) module is to provide a vocabulary for users with correct permissions that only they can edit and use.
A secondary goal is to make the vocabulary/term interface easier to use, since this permission can be given to non-admins.