Going to GS1 is fine, but frankly, their application process is time consuming and stupid and they are a huge rip. I took this route for my first products and ended up paying for15 bar codes $1500 to register, then $150+ (depends on your sales) every year. That's a lot.
I sell products on a variety of retail sites and have used the 'verified resellers' that are mentioned above (I use www.nationwidebarcode.com, and am most envious of his business that just prints money). If I have an issue, it will not be difficult to pay the $$ to GS1 at that time to get a really extra super valid code. Will Amazon/Wallmart boot me for a clerical error? I don't think so.
It's difficult to tell what sites are really legit as any one of them can easily fake your 'certificate of authenticity' and any list you find of firms that were part of the lawsuit refered to in the other answers. To be frank, I don't have the time to vet these firms and if they are fraudulently selling me UPCs and it does me actual damage, I'll go after them at that time, class action, etc.
Advice from someone who went the cheap route and hasn't gotten into trouble yet, get your code cheap and get on with doing things that you need to be doing.