Pipe bursting has been around for years. Here is a nice in depth video demonstrating its operation. I recommend using HDPE but if the space allows for it, you can use PVC, its just more work. Just look up Vermeer's Hammerhead Mole if you're curious to see more about it. This method is available in many sizes and types of pipes.
http://www.youtube.com/watch?v=iiEeJ9fBHqc
Like stated above, you cant just go dig up the street at random. You must atleast have a right of way permit and to get that, you need to be licensed, insured, and bonded.
I'd say the only ground you have to challenge on is if they had been using a boring machine in the vicinity, and clipped the top of the pipe during a different, unrelated installation causing its failure, then its on them. Most new installations these days have laterals already put in and terminated at the edge or outside of the right of way for a plumber to take over later and finish once the house is constructed. So if its close enough to the main, it could be their problem. The thing is, the utility itself wouldnt do these repairs in a big city, they would sub them out. Of course both of these would be irrelevant in an existing utility situation.
Its cost depends on how deep the sewers are, they can be 5' or 35' deep. Before you buy, dont be afraid to go out in the street and open up a manhole or two and take a look in a safe manner. it might save you some $$.