Well it makes sence that there is something wrong with the user accounts, I had a new user sign up and things went wrong with his/her register. Showed that the account existed, however they could not logon so I manually deleted it then got them to re-create. I likely broke the user account, now I will need to fix this, let me have a look and see what I can figure out. Thanks for the help, I will let you know if I got it working or not.

 I manually went in using SQL Management Studio (2005) and ran that SP.  There are three input parameters and one output.  Two are obvious - portal and userID.  The third relates (best I could tell) to the different membership tables involved.  If you review the SP, you will see what each option does, and basically to fully delete the userID, you run teh last option - all tables.  I just ran it four times - one for each table, and it deleted the user ID fully from DNN and asp.net membership tables.  Be careful on that if the ID is in different portals - you do have to specify the portal, but I'd test this with a dummy user on a test system/db.  I did on mine (it was a sandbox anyway in a different DB) and it worked perfectly.  Not elegant, but it worked. 
If you have SQL 2000, use Query Analyzer to run the SP.  I'm sure you know how, but if you need any help there, just post back and I'd be happy to assist.