Got it Working (Not 100% sure what did it)
Ok, I fixed my issue but I'm unclear of the exact action that fixed it.
When I first set up the phone I didn't complete the wizard all the way through, I believe I exited partways and then added accounts afterwards. I'm not sure if it's related but I thought I'd preface what I did with this information.
I ended up backing up my card and then erasing its contents, but that didn't fix the problem. A support email with google returned with a response to erase the market app's cache and undo any updates but that didn't help either.
I finally went to the factory reset and completed the wizard in its entirety, adding my gmail, htc.com, flickr, and facebook accounts. After everything synced it gave the message that it found updates for my apps and now it looks like its downloading again.
The first app I downloaded doesn't seem to work with the Evo 3D (Easy Profiles), but the Amazon.com mobile store app worked fine.
Good luck.