Did you replace the water pump when you replaced the timing belt? It's recommended.

I was told in the past (not sure I believe it though) that the fins on a water pump can erode over time/use. If that were to happen though, I'm guessing that it would show the symptoms you describe.