iPhone 4S linked to old Apple Id
Remove it from the iCould via Web Browswer

You'll have to log into icloud.com with the AppleID that the phone is locked to.  

Click on Find iPhone.  It will bring up a Map and try to locate all of the devices linked to that AppleID.

Click on All Devices drop down at the top.

Click on the iPhone 4s in question.  It will have the name of the phone (for example - Users iPhone)

Click Remove from Account

Next time you reset the device it will no longer be linked to that Apple ID.

Remove it from iCloud on the Phone

If you can still get into the phone. Follow these Steps:


Open the Settings App
Touch iCloud
Touch Find My iPhone
Turn Find My iPhone to Off Position
Enter the password of the iCloud account
***Note - these steps might be slightly different depending on iOS version


Next time you reset the device it will no longer be linked to that AppleID.

Just FYI iCloud account and AppleID are synonymous these days.