How can I take control of these sites through Contribute so that I can start administering them? Is this related to the removal of the old Admins account?
Yes, it is related. Setting up a co-admin or sub-admin is all well and good but if the primary admin account is removed before you fully transfer control, Contribute may throw a mild fit.
There are a couple of things you can do to regain control. The easiest one is to connect to the site using Dreamweaver and go into the Site Definition | Advanced Settings | Contribute and set the Contribute Administrator there (and do any other housekeeping while you're at it). Dreamweaver automatically assumes you have the ability to manage Contribute and overrides any settings in Contribute that is protecting access. If you don't have Dreamweaver installed, Adobe does make it available as a full-featured 30-day free trial so you can download and use it for this purpose without buying the whole thing.
The slightly more difficult and severe approach would be to kill Contribute control entirely. Login to the site via SFTP and look for the _mm folder in the root. In that folder you should see a file
cthubXXX.csi. Deleting that file will completely remove Contribute from the site and you will have to start over defining users, roles, permissions, etc. Take a backup before trying this step.