First let me caution that I am no Ubuntu Guru!

I have Karmic Kubuntu 64 on one of my systems and once had Tweetdeck on it.
I can't recall why I took it off, probably just wanted a simpler solution,
but thought I'd try re-installing to see if I could duplicate your problem.

So, like you I'm sure, I went to the Tweetdeck website downloads section and
clicked on the download button. I had cut right to the chase by choosing the
"download" item from my Google search, not completely sure if I was going to
wind up with a Windows executable, but all worked just as it should. In
short, it installed Adobe Air and the application which worked the first
time.

The only tiny glitch was that there was a window requesting permission to
use my saved password which was hidden under other windows.

So I can't help you, except to suggest that you remove everything and try
again. It does work for me on my 64-bit Karmic Kubuntu machine. I can't see
how it could be any different on Ubuntu, but having said that I know
different hardware/software configurations sometimes do conflict.