"Invalid SIM Card" (iOS 5.1)

There will still be people who have this problem so I'll post my findings for reference:

There is a piece of software on your phone that communicates with the microSIM card using a certain protocol.

You can see details about it on the Settings > General > About screen, and look for Carrier.

Mine used to say Carrier: Orange UK 11.0, and iOS 5.1 bumped that to 12.0.

That version bump affects old cards, especially those who were never a microSIM in the first place (say you chopped the card to size yourself). The engineers' assumptions about microSIM kick in, so that's normal. Thus my very old SIM card (cut to microSIM of course) stopped working. Merely because at 8.5 years it was too old. Verified that by inserting a more recent SIM card in (also cut to microSIM) and everything was fine.

The phone should have said "Unsupported SIM card" but of course it doesn't, and goes into "No SIM installed" which is obviously a bug on their part.

If anything like this happens to you, just go and get the microSIM changed by your cellphone company. Since 5.1 is so new at the time of writing this, you will likely have trouble convincing them that they owe you a new microSIM, so you may have to just pay for a new sim card, and save yourself time and arguing.