iPhone 4S bought "unlocked." Worked with Straight Talk, not in France.

after buying it unlocked on Amazon.

A very unlikely scenario Amazon are not authorised resellers and You almost certainly have a carrier locked iPhone

As a general statement the only source of unlocked iPhones anywhere from new is an Apple retail Store or Apple.com regardless of the country

The third-party would have had to hack the iPhone to "unlock" it. No shop or bulk reseller can get an iPhone officially unlocked. So if it was actually unlocked at all and you just weren't lied to, any update since would have re-locked the iPhone to the original carrier, and only the original carrier can officially unlock it.

Regards.

You will have to try and find out who the device is locked to. Did you do an update on the phone before you inserted this French SIM? More than likely as Peter said, the device was hacked before sold and the device has locked back to the carrier it was locked to.

The iPhone was therefore hacked ( jailbroken ) to unlock which has allowed use on Straighttalk

You likely updated the iOS and that locks back to the carrier it was hacked from

No help here for hacked iphones you are on your own I am afraid

An AT&T locked phone will work on ST because ST uses the AT&T network.

If someone is a current customer of AT&T, they may unlock the device, but the decision is AT&T's.

Here are AT&T's official requirements for unlocking an iPhone:

http://www.att.com/esupport/article.jsp?sid=KB414532&cv=820#fbid=7eivX4S6I8c

and the procedure:

https://www.att.com/deviceunlock/client/en_US/

Regards.