@Jesse:
...
$ apt-get remove xserver-xorg-video-nouveau
E: Could not open lock file /var/lib/dpkg/lock - open (13: Permission denied)
E: Unable to lock the administration directory (/var/lib/dpkg/), are you root?
...
You missed to put "sudo" in front of the command
sudo apt-get remove xserver-xorg-video-nouveau
Even if your case maybe is not fully identical to bug 721306, removing xserver-xorg-video-nouveau should help solving your 'held package' problem.
@Jesse: xorg-video- nouveau
...
$ apt-get remove xserver-
E: Could not open lock file /var/lib/dpkg/lock - open (13: Permission denied)
E: Unable to lock the administration directory (/var/lib/dpkg/), are you root?
...
You missed to put "sudo" in front of the command
sudo apt-get remove xserver- xorg-video- nouveau
Even if your case maybe is not fully identical to bug 721306, removing xserver- xorg-video- nouveau should help solving your 'held package' problem.