You can remove the windshield yourself, just cut through the old seal with a razor knife. I haven't had the best luck with the parking lot guys either, but I don't know that this is necessarily their fault. Well OK, the guy who scratched the A pillar was at fault, but other than that guy, I think the problem is the seals are crap. I had a new aftermarket seal and the windshield leaked every time it was replaced. I found that the easiest way to get the windshield to seal was by taking a tube of clear silicone and putting the tip UNDER the lip of the weatherstrip and putting a bead in underneath the gasket. Worked well and didn't leave a bunch of goop all over. The other problem I had was that the sheet metal underneath the seal was rusty. I think this is because the seal let water in, but my silicone job wouldn't let it out.
With your car painted already I think you're just going to have to hope that your old seal shrunk and that the new seal will overlap the color change. I don't know of another way to fix that issue, aside from painting that area again if the seal isn't big enough...