Hi Daniel
We will do some digging into this today to see if there are other reasons for this error, but seems to indicate that you may not have rights to install the webpart into the gallery on the desired Virtual server. The fact that stsadm had the same issue seems to verify this.
You can verify you are a farm administrator thru the central administration site for your server.
Click on operations, then Update Farm Administrators. If this doesn't help please let us know as we will have to dig in deeper.
See Attached