Do you know if FusionIO drives internally run as Raid5? Not your external Raid0, but since flash chips are so relatively small in capacity right now, they must using an array internally, maybe Raid5?
If so, Raid5 has a severe performance penalty when very small amount of data are being written (smaller than a single stripe) because it has to then go update the parity across the volume on every write and that defeats any caching.
We already know ALTER itself is slow but I wonder if your storage is working against you in this case because ALTER does a single write for every row in the column when rebuilding the table...?
If single core is the problem, throw a massive clock rate at it?
The i5-680 is out this month and is 3.6ghz native ("turbo" near 4ghz) should do 5ghz with good air cooling (it's 32nm) and then you could use ECC memory to be certain in a mission-critical environment?
Intel(R) Xeon(R) CPU X5570 @ 2.93GHz
So it was a pretty high-end Nehalem proc already. And, yeah, we do have ECC RAM in the box, of course. Plus InnoDB does page-level checksumming to guard against corruption too.
But still, it was ~8 hours or so. Using all 8 cores on the box would have brought it down to ~1 hour if it could have been perfectly parallelized (and much of it could have been, I bet).
As far as the parallel cores it sounds like you already have thought about possible "end runs" around MySQL's "transaction safe" ALTER (which is probably why it's single threaded). InnoDB supposedly has a few performance improvements for ALTER over MyISAM so you are already taking advantage of that.
We just did a lot of ALTER TABLE work on one of our clusters WITH fusion-io drives (2 in a RAID-0) for a 360GB table and it still took ~8 hours to finish.