First of all, you shouldn't take the prices on wire services websites as the price everyone pays. In my experience, these can be discounted 50-75% if your account rep is hungry believes you can be more than a one-off client.
Second, you should take a hard look at how news-worthy your release is to the general public. If you're announcing a rewrite of your webapp into scala, then you should skip a press release and just target the handful of outlets in your niche. This can be a hard one to do since you may have spent the last 10mo tirelessly devoted to feature x and it's all you and everyone at your company talk about. Strive to regain focus and take a critical look at how exciting the mass media is going to find your announcement.
I've never just used a wire service and expected results. If you are a small startup and are really announcing something that meets the criteria of the paragraph above you'll probably land a few hits - small blogs, regional print, maybe a trade pub. Wire services should only be a small part of your strategy for announcing a new release.
The direct outreach is the most important for real results. Hopefully you've been building a list of media contacts that communicate relevant information about your industry, if not start now. If you haven't already, sign up for HARO (http://helpareporter.com) and look for reporters who are actually looking to write about things your company does//makes//gives away.
On the day you release your update, I would send an email individually to those people on your list. Write them a short, personal message explaining what you've announced and why it's interesting. Add the text of your press release below your email and make sure to include ample ways for them to contact you (cellphone, aim, etc) if they're interested in any followup.
As for writing a press release: very few PR people will understand what you're doing as well as you. On the other hand, those people spend all day interfacing with the press you're after, so they have an idea of how to effectively communicate with them. I would suggest the best writer on your team takes a stab at writing the press release. Then pass it around for folks peer-review it (friends, girlfriends, english lit majors, whatever). Don't be afraid to cut down the verbage. Don't over-inflate your accomplishment(s). Don't use geeky terms.
One thing I've had great success with is teaming up with a college student who wants to get into PR. It's a great opportunity to cut their teeth on something real, and for you to have someone else obsess about the wording in the release while you manage the 500-or-so pre-release emergencies that tend to crop up.
Lastly, you should also take a look at marketwire. I've had experience w/ most of the wires you mention and mw was my fav for tech.