I've seen quite a few things before but this one really beats me. Earlier today I installed a Promise TX2 Sata 300 PCI card and replaced on of my Sata disks. And now the whole disk layout appears to be confused.

This is what I had before:
sda: Western Digital 250GB Sata II - Mandriva (xfs), Debian (xfs), openSuse (xfs), PCLinuxOS (xfs + ext3 boot partition with GRUB menu)
sdb: Western Digital 250GB Sata II - Win XP64 (ntfs), Solaris 10, Fedora (ext3/fat32), Sabayon(xfs)
sdc: Western Digital 250GB Sata II - data partition (ntfs & mainly ext3)

sda + sdb were connected to the first two Sata ICH8 ports of the ASUS mobo, sdc to the third one (which is not bootable).

Wanting the third disk to be bootable as well is one reason that made me install the Sata PCI card. I had used an ATA PCI card before and assumed it would be cake walk. I moved sda to the first port on the card, left sdb on the ICH8 and replaced sdc with a 500GB Samsung Sata II and moved that one to the second Sata port on the PCI card.

I booted into Debian off sda (where GRUB resides) and I immediately got
"fsck.xfs failed"

The same or something similar happened when I tried booting any of the other distros. I tried repairing xfs by running
xfs_repair dev/sdXX
on all the xfs partitions.

Then I was finally able to get into Debian. Phew, problem solved.

Well no, not really, the other distros are still refusing to boot and now give me error 22 and kernel panic - not syncing.

What immediately struck me is that the booting process seemed to be addressing the wrong partitions. According to fdisk -l on Debian, I now have:
sda = 250GB Sata2 (which must still be the old sda because I can boot Debian off it)
sdb= 500GB Sata2
sdc = 250GB Sata2 (the old sdb)

But: when I tried to boot, say, Fedora off sdc, I saw it was trying to mount sda2 while all its partitions are on sdc

That got me suspicious so I checked disk order from a PCLinux liveCD. This is what it reports:
sda=250GB (ata-piix) = the old sdb
sdb=250GB (promise_sata) = the old sda
sdc=500GB (promise_sata)= the new disk, shown as sdb by Debian

So PCLinux is reporting a completely different ordering and I suspect something similar is going on with the rest of them. At the root of it all, there appears to be disagreement over precedence: Debian thinks the Promise controller should come first, PCLinux thinks it should be the ICH8 controller.

Yes, I could switch disks, edit /etc/fstab... But how would that help when two distros on the SAME disk appear to take such incompatible views.

So: I'm really really stuck right now.

Sounds like fstab issues.
The BIOS determines the disk order. You need to find out what it is presenting. You may need to adjust device.map and re-install grub, although that generally isn't needed.
If 'twas me I'd boot something like Knoppix and check what it sees - then adjust the installed distros to suit.

Well, it is more complex than that. I have four distributions on the first hard disk (first, that is, according to BIOS) but only Debian reflects the ordering set in BIOS and identifies sda as the first disk; the other three agree that sda = the third drive specified in bios.

Which explains why I'm completely puzzled: with the same bios settings, how is it possible that one system reports one sort of ordering while the other three use a different one.

Linux/Unix distributions differ with each other in the partition order/disk order they display or handle.
I have faced this problem a lot of time while installing different Linux/Unix distributions.

The way out will be to change the fstab information in the distributions as identified by them. This can be done by booting the distributions with their respective boot disks and 'chroot'ing into the distributions.