Forum moderator, "lapetus," over at NeoGAF decided to take matters into his own hands by invoking European consumer protection laws in a complaint filed to Amazon, where he'd bought his PS3. The tactic earned him a refund of £84 from Amazon without physically returning the console. The law in question, Directive 1999/44/EC, is placed on retailers, not product manufacturers, and states that goods must "be fit for the purpose which the consumer requires them and which was made known to the seller at the time of purchase."
Sony might argue that the firmware update wasn't mandatory, or that it changed the console's software and not its hardware features. But if a raft of similar complaints crop up then retailers could attempt to pressure Sony into paying the bill or re-enabling the Other OS functionality. There's no such law in the U.S. as PlaystationUniversity.com points out, but I wouldn't be surprised to see a class action suit filed against Sony for the removal.