Deutsch für Doofe

Well, just don't do as I do: Es tut mir leid, ich sprechen nicht deutsche! Ich verstehe nicht!

This reminds me of a friend in college who learned some german while stationed in Germany. After his tour with the army ended he came back to the US and went to college. He was taking a french class and the professor told him he was speaking french with a german accent.

That was über-hilarious. ;)

This person is quite good. I didn't notice any accent until he said "Schornstein". He pronounced "Schoenstein".

Das ist ganz ueberraschend. German is actually quite easy, especially since it shares so much of its core vocabulary with English and has only a moderately difficult grammar. Everything else is pretty straighfoward, including the spelling. I still can't for the life of me spell through a paper bag in English, but even the longest words in German aren't a problem at all. Sagt es mit mir!

Geisteswissenschaft!
Fangschreckenkrebs!
Einbahnstrasse!

Do you want to switch places with me for a while? I crave immersion. :P

Not a video, but might I suggest livemocha.com for help learning German.

Es hilft nur üben, üben, üben!
Phrases alone aren't enough, of course. Did you ever had some "formal" training in German? I really helps to know how those pesky german verbs and tenses work etc.
Depending on your learning style, a classroom setting might be helpful.

I live in Hamburg, so I can't easily visit and make you speak German. [eg] I have given classes in "Deutsch für Ausländer".

The BBC has some good stuff for learning German: http://www.bbc.co.uk/languages/german/index.shtml

I would also suggest watching clips of the Wochenshow on Youtube. They're always a hoot and it's hard to forget any German once you've seen it on the show! "Spiel ums Leben" is my favorite clip, followed by "Der Propellergorilla".

Heh. It seems like your foreign-language use module* is kicking up but hasn't yet found the right mode. I think that happens to most people in your situation. That my fellow countrymen seem to be a bit brusque, I'm sorry for.** They shouldn't be.

*No idea whether some anatomical partition like this actually exists in the brain.

**See, it's easy to write German! :-)

Are you reading a lot in German, or mostly in English? The former may help to get your bearings better. And on the speaking front, in Frankfurt there should be some Stammtische (no real equivalent in English, perhaps close to the community at the bar in an English pub) of expatriates and students who practice their German. They should be about as "bad" as you and very likely more forgiving since their learning period was more recent than ours (Germans, that is). Lastly, do you speak German at home? It might be fun since you don't really have to.

OK. Enough advice. Take it with a grain of salt. I'm reading and writing mostly in English, but since living in Germany my prose has taken on a German quality (sentence construction, especially). On the other hand, my colloquial German is peppered with English phrases like "Thank you" and sometimes it actually feels like a reprieve to speak English here. But then I can't think of the English words! It's all rather confusing.

I cannot believe that Mark Twain's fantastic "The Awful German Language" has not been mentioned here (or have I overlooked the reference?). A must for everyone who understands English and has at least some notions of German.

I highly recommend "The Awful German Language" by Mark Twain:

My philological studies have satisfied me that a gifted person ought to learn English (barring spelling and pronouncing) in thirty hours, French in thirty days, and German in thirty years. It seems manifest, then, that the latter tongue ought to be trimmed down and repaired. If it is to remain as it is, it ought to be gently and reverently set aside among the dead languages, for only the dead have time to learn it.

http://www.crossmyt.com/hc/linghebr/awfgrmlg.html

So I am too intimidated to attempt to practice speaking my piss-poor German because the Germans are not very forgiving of idiots

Don´t be so intimitdated, we´re not all such jerks! Just speak and practice, it´s the best way of learning German. Try and error!

Just keep trying and learning, but most of all you have to speak even if you think your pronounciation etc is terrible. Practice makes perfect!