After about 6 hours of investigation I have fixed a very annoying bug. To say I fixed it is not quite right, I was using a version of the pinChangeInt that gets you interrupts from any IO Pin, it worked great on pins 2-7 but not on 8-13.
The library was not reporting any errors, so I took a look at the underlying pin change interrupt registers and found they were not being set. On the off chance I downloaded an the latest version of the library to find it includes some documented bug fixes and now works on both ports.
EDIT: Added link to google code group here - http://code.google.com/p/arduino-pinchangeint/
Again, this might save someone some time.