When I first read PSS, I must admit that, although I enjoyed it, I did not see why everyone seemed to be raving about it. It was after re-reading it, prior to reading the scar, that I really 'got' PSS, and saw it for the superb book it it.
I think this is because, as others have said, that you are plonked into world and it feels like the book assumes you know what the back history is, but you don't. When you re-read it, you understand it more, and the book really does shine.
If you are reading it and struggling, please persevere, and the second time it'll really be worth it.
Mr Mieville, if you are reading, can we have another story set New Crobuzon? That'd be lovely, ta.