Did you try out the new iTerm? I was having issues like this, and started using the iterm nightlies about 8 months ago. I've seen considerable performance improvements, and now prefer it over Terminal.app.