PRWeb is probably the best press release distributor, as far as PR for SEO goes. People do read them, they rank well, etc.

I agree with the others, with reservations: the thing to remember about SEO is that the results compound; if you bring in 20% more visitors with your off-site marketing, and you get 20% higher conversions with your on-site redesign, that's 44% more customers. If you're going to do a PR, make sure you have a blog for your new visitors to read, too.

(Incidentally, I work at a company that does SEO, including press releases. Email address is in the profile).