I have many other apps which have updated after the release of 4.0. The other apps state "iOS 4.0 tested" and Requires iOS 3.0 and later. So, I think you did something wrong because if that was the case, every iPhone app update after 4.0 release, would have broken compatibility with anything lower than 4.0.
The bottom line, your app stopped working when you released an update, and the rest of the 175 apps on my phone still work after the developers updated their apps. As for the statement "This behavior is not documented anywhere so one only finds out after it's too late." You might want to check with Apple concerning backward compatibility, it exists.