Hard to say without a pic,
could it be a CARNIOLAN?

Carniolans are almost black.
Konrad

Here is a link that might be useful: CARNIOLAN

Laura,
If you're in the north Texas (DFW) area, we have several beekeepers keeping Caucasian and Russian honeybees which tend to be black/dark grey as opposed to the more typical Italian strain with yellow/gold bands.

No it isn't the Carnolian. Actually it doesn't have any striping on its abdomen at all. I got a really close look at one yesterday. Solid shiny black, not hairy, black wings, black face/head and legs. Its abdomen is more rounded than a honeybee (more like a Carpenter bee's). It is what I would describe as an "agitated" flier. It moves more quickly than a honeybee and seems to not like me getting close. The only color on it is the pollen on its hind legs. This is really a puzzle to me. I thought I knew most of the insects in my area. A lady at a local nursery said that she has seen them this year too and has never seen them before. Could this be a type of Mason bee?

The pollen carrying sacks on the hind legs still indicate a honeybee as this is a very specialized way to carry pollen and requies the development of the pollen combs on the midlegs. You can check out the following Texas A&M website to see if you spot anything closer to what you've seen (index 14).
http://entowww.tamu.edu/images/insects/common/index.cfm

This sounds like a Mason bee?
Konrad

Ive seen a bee just like you describe around my garden lately. There are no commercial beekeepers in my countty and my area is new construction in a feild so id know if there was a bee hive around for atleast a mile.

It is interesting that they are just showing up in areas that they haven't been seen before. I just wish we could identify what type they are.

At www.bugguide.net there were several types of wasps that look just like bees: more rounded head, abdomen close to thorax (no noticable waist), all black, no hair, etc. You might check there.

On the left, click on the bug that looks like a wasp (and where the tool tip says wasps). Click on the "Browse" tab to see sub families.

Definitely not a wasp. I'm leaning toward an Osmia of some kind. Do they have the capability to carry pollen on their hind legs or is it only the honey bees?