Someone who bought my old phone asked me to remove my icloud account. I went to manage devices and removed from there via ITunes is that the correct way to totally remove it?
That's the problem.
You had to go in and remove the icloud account and the find my iphone feature before you did an erase all.
I bet there will be millions of iphones sold and will be in the same situation as yours from now on with the new security feature added with ios 7.