That's a perfect example of the problem: it'd make it harder but far from impossible to cheat (cheap SIMs, spoofing through insecure telcos, etc) and there are a non-zero number of legitimate users who don't want to give Twitter a phone number.

You'd probably need some sort of hybrid approach to do this for real – SMS validation counts as x points, y months of interaction with other users without a complaint counts as z points, etc. It's similar to the email anti-spam measures but a less daunting problem since they don't interoperate with many thousands of other peers (for better and for worse).