After the latest 0.36 tweetdeck update, Tweetdeck has included their beta real time streaming of tweets in their standard release. This caused normal users to face many problems. Since real time streaming of tweets causes more twitter api requests per unit time to fetch tweets. Which often causes exceeding the twitter api limit and therefore you'll notice that your stream will pause for about 15 minutes sometimes more, renders a few tweets and then pauses again , ... etc) + tweetdeck showing you the "twitter api rate limit exceeded" error at the bottom right.
You probably won't face any problems if you are just a normal user who just keeps track of his main twitter stream. But if you have many lists that you have added as columns via tweetdeck to keep a close eye on, You'll face this problem. To be honest, it was pretty confusing to me as well as I did check "Allow tweetdeck to automatically manage my api limit" under tweetdeck settings. And therefore, I assumed that I shouldn't run into any API problems. Apparently, tweetdeck selects some columns such as a few lists and your mentions column and enables real time streaming on those too which is not a good idea.
Summary is, tweetdeck real time streaming hasn't been perfected yet. Until then, A solution to your problem would be to disable real time streaming by going to your tweetdeck settings -> twitter and then uncheck enable real time streaming, Like the following picture demonstrates:
This would revert back to the old tweetdeck style of retrieving tweets like in versions prior to 0.36 =)