**Resolved
Well after a week of posting on PSN's Forums, I thought I would try here. If there is a better place to post, let me know and I will move it there.
Ok, so I sinned. I needed a electronic device, and rather then research and find the best product online, I impulse bought a headset for my PS3 at Walmart. Obviously, it did not work out. Here is what I tried.
A. I have gone into 
(Settings) > [Accessory Settings] > [Audio Device Settings] and set input and output to the new headset.
B. It shows up as "Logitech USB Headset"
C. A mic test comes up fine. Good Dhb levels.
D. Device is USB Certified; the only requirement I can find on Sony's site here.
E. Even though I had UPNP on my router, and all the extra ports forwarded, I bypassed the router completely.
F. Made sure Voice Chat was enabled in my game.
G. Made sure mute wasn't on, and volume was up
H. Try a disconnect and reconnect of the USB while PS3 powered on.
I. Tried it on my PC. Connected with no driver (Past or present) and on configuration. Recorded and played back sound.
Here is my train of thought. The fact that I can hear myself when doing a Mic test tells me its not a hardware failure. The fact that I can hear others, but they can't hear me, and I can't even hear myself, tells me its not a connection problem. It sounds like compatibility issue between the way the USB plug and play driver communicated with the game. I have done some research, and have seen a lot of people having a similar issues. Here is what I am going to try next.
1. Try a bluetooth headset. I have one for my phone I could use.
2. Send a voice message to a friend through XMB
3. Call up Sony Support.
4. Call up Logitech Support.
I just don't have high hopes that either of those tests will lead to any productive results. Your input would be much appreciated. Thank you.
If link did not attach: http://playstation.custhelp.com/app/answers/detail
