I agree with FK in that Dylan Moran would make a great cabby. He's not exactly what I pictured, but I have the feeling he could pull it off really well. He has the kind of look that would work well for both his role as a Cabby and afterwards, when he is King Frank.
As for Sean Astin, I'm a huge fan of his portrayal as Sam, and I think he could do a great job at portraying the Cabby. My only concern is that he was already in LotR. This isn't necessarily a bad thing, but the way I see it, it could go both ways. On one hand, it might not help establish Narnia as a separate story from LotR, but on the other, it might help draw in more viewers since pretty much everyone I know is a fan of Sam.
Also, Michael Sheen looks like a good fit, too! He also has a cabby-turned-king sort of look, which is probably the most important thing I'd like to see in whoever ends up playing King Frank.
I'm actually not too partial as to who plays him, as long as we get to see him in the movie regardless.