Thanks to Renay's strong recommendation, I finished this book today and liked it quite a lot. I had the same issues with the romance as you both did, although at least we see the very very beginnings of Andevai recognizing that he was terrible to Cat. If the book had ended with them really truly reconciling, I would likely have thrown it across the room. Also a few points off for the cliffhanger.

Have either of you read Un Lun Dun by China Mieville? There's some interesting compare and contrast there to Cat and Bee (which I agree was one of the best things about the book).