I decided to do some more of my own research on this with the nitrate/nitrite confusion. Thanks to the other answerers, that definitely helped give me a good starting point. I'm writing my own answer so I can include some links. I made it a community wiki (seemed like it might be good for this one).
Firstly, from everything I've been able to find online (wikipedia has remarkably little info about nitrates/nitrites as applies to meat curing) there is no substitute for the nitrites. They occur naturally in many vegetables, so when used appropriately they don't pose an undue health risk. Nitrates/nitrites are added to meat cures (at least historically) largely for their preservative qualities. So, in a corned beef brisket that is going to be brined then cooked and consumed immediately the nitrites are unnecessary.
Also, nitrites do make the meat turn reddish when cooked. Opinions seem to be split as to whether there's a significant impact to flavor in meat brined with nitrites for a relatively short time, say around a week. But since the flavor development is unmistakable in longer curing processes, I doubt there is zero effect on flavor even with a short brine.
As Bob explains in his answer, nitrites are the preservative, and potassium or sodium nitrates are converted into nitrites during the cure. I'm guessing that saltpeter (potassium nitrate) was used more frequently than sodium nitrate/nitrite in the past because it was more readily available. From what I've been able to find online, it's no more available now than sodium nitrite preparations, which are more appropriate for this kind of meat curing.
The sodium nitrite preparations are often called by the generic name "pink salt" because they are colored pink to avoid confusion with regular salt. The brand names I've found online are Insta Cure #1 and DQ Curing Salt #1. The #1 indicates a preparation of 6.25% sodium nitrite and 93.75% regular salt. Pink salt #2 indicates the preparation also includes sodium nitrate. #2 is only necessary when dry curing like pepperoni and dry salami, which are not cooked or refrigerated. Pink salt is used in small quantities in addition too, not instead of, regular salt. (Most brine recipes I've seen use 2 cups kosher salt and 4 teaspoons pink salt.)
It seems like there are two widely available books that people recommend for meat curing: Charcuterie, by Ruhlman, and this one (which seems to get the hardcore purist vote), by Rytek Kutas. I don't own either, so can't recommend one, but Ruhlman does have a blog where he posted the corned beef recipe from his book. Best of all, the blog post has a link where you can mail order the pink salt, and it's way cheaper than the small handful of other online sources I've been able to find.
Finally, note that saltpeter is poisonous and flammable (it's used in pyrotechnics and to burn out dead tree stumps). Sodium nitrite itself can be fatally toxic if a human were to ingest an amount equivalent to 4.6 grams (citing from wikipedia), which again is why they make the curing preparations pink. Given that, there is no way I'd use the 99% pure form of sodium nitrite even if it is labeled food grade. I'm no where near good enough at math to be sure I wouldn't kill myself with it. (I found a hunting supply website that sells that stuff to use in curing fishing bait.)
To sum up, it seems like sodium nitrite is worth using but can be omitted, it has no reasonable substitute, and it's unfortunately not easy for most of us to come by. Thanks again to the commenters and answerers.