Tobb,
I would recommend getteing a camera to locate where the problem is before excuvating your yard. If the pipe is to full of water and cloudy to see, get them to jet the line, then go in and see whats going on. I seriously doubt that the city jetting their main is the problem, your neigbors would be stopped up also. Where I live, there is alot of problems at the sewer tap, if this is in the street, this could be the citie’s problem. Down here, people are only liable for their sewer lines to their curb, once there, the city responsibility.