A follow-up to this: it seems that the ATMega168 is the solution to this. The I/O pins on this chip can be used as external interrupts, giving you a total of 26, without priority encoding. This, together with the increased flash ram, makes the 168 a very useful part. I'm joining the apparently long list of people waiting for the Bluetooth Arduino.