Though the details are not published yet, the currently known information points at the following: some sensitive operations are protected with some encryption and a MAC, both relying on carrier-specific choices of algorithms and key lengths. However, some carriers apparently rely on DES whose key size is relatively small (56 bits), making key recovery in reach of dedicated groups, even amateurs (with some budget, but the effort is said to be shareable through the use of rainbow tables).
The important word is "carrier-specific" and it is very unlikely that carriers would actually disclose what they are using. The reflex of security by obscurity is well entrenched, especially in times of rumoured crisis.
Generic note: from a cryptographer point of view, there is the tractable and the intractable. This is normally a continuum: larger keys make the attack more and more expensive, and there is an attacker-specific threshold beyond which the attack cost makes it no longer worth the effort. Precomputed tables (e.g. rainbow tables), when applicable, can transform the "tractable" into "cheap (on the long run)", which implies a huge gap between the two worlds: there is now the "unbreakable" vs "everybody can do it".
However, it is possible to design algorithms which are tractable (attacks can be made to work) but cannot be optimized with precomputed tables. Typically, password hashing with salts falls in that category. Though a reasonable fix for the SIM card attacks would be to switch to a strong algorithm (even 3DES would do the job), it is possible that carriers implement short-term solutions involving some randomization with public values -- making their SIM still potentially attackable, but with a high cost per attacked SIM (a 256 exhaustive search, while doable, is still expensive; try it on your PC !).
On performance: a rainbow table is about exploring a space of N values, but storing only N/t of them where t is the "chain length", chosen at table construction. When using the table, you need to perform t lookups (and there is a per-attack t2 cost). A mechanical hard disk can handle about 100 lookups per second. We are talking about a 2-minute attack, hence 120 seconds, and the attacker might have brought, say, 10 disks to the dance. This allows for a t equal to 120000 or so -- let's say 131072 (217) to make computations easier. With N = 256, the attacker still needs to store 239 elements, with a cost of, say, 10 bytes per element: we are talking about 5 terabytes or so, which is cheap by today's standards. The CPU cost is then 234 encryptions upon attack, which is probably achievable in software on a couple multicore PC (with some nifty optimizations) within the 120 seconds time frame.
Thus, the announced figures are plausible, with a small budget. The initial table building, though, would take some more muscle (months with a rented cluster); existing rainbow tables tend to concentrate on password hashing functions, not raw encryption. Rainbow tables on generic DES must exist somewhere (it is the kind of computing feat that Secret Services around the world would be proud of), but maybe not easily obtained by amateurs.
