then how else could you explain my icloud contact list becoming empty overnight when I've done nothing...
The person you sold the phone to couldn't of done anything to your contacts. They can only delete them off of the phone they have, not remotely on the one you have now. I would either call the number already listed or retore from the January backup. It doesn't matter if you have a 4S and it's from a 4.
Only if you did not properly restore the phone and remove your iCloud account from it etc.....if you did not, you only have yourself to blame!
This is a good lesson in learning why you should back up and you should wipe your phone before selling it. I can only imagine it had to be something on your end and not your old phone. Had it been your old phone I think that you wold have seen the new owners contacts pop up. Only thing I can think is you turned of the contacts in icloud settings and then deleated them off the phone. If you haven't backed up to icloud since you lost your contacts you might be able to do a restore and get them back. But that would only work if you HAVEN'T BACKED UP TO ICLOUD SINCE YOU LOST YOUR CONTACTS. Good luck