We've had this problem since the very beginning (2 months ago). Out tag cloud displays only the tags we introduced first and even though some of them are not that popular (for example we used them only once), there are still displayed in the tag cloud rather than the ones that were used later a couple of times.
I know that the tag cloud displays only 45 tags, but in our case they are not the most common ones, just the ones we used first. It just simply doesn't update.
Does anyone know how to solve this problem? We looked in forums but we couldn't find any solution and I don't know what else we can do :(