Now when I try to use the paint weights tool, I get an error that says a muscle deformer has to be applied to the geometry, but I already did that...your basic issue is that when you first modeled you probably never laid out your UV's and since Nurbs already have UV's this is what solved the issue for you.
When binding a rig each joint gets assigned a vertex which it has influence over or several joints with various weights that add up to a total of 1. To correct your problem you have to paint correct weights to the vertices for each joint the is causing you problems using the paint weights tool.