The laws vary from state to state. I'm not going to read them all. Here are the laws in my state: http://www.kansas.gov/ksbtp/statutes.html Specifically pertaining specifically to who does or doesn't need a license: http://www.kansas.gov/ksbtp/74-7035.pdf

I've always thought a phlebotomist is similar to a licensed electrician. (Assuming an MD is similar to a PE)