Do permalinks mess up tag clouds?

I’ve had a problem with my tag cloud (links from tag cloud are not working correctly) and am wondering if it might be because I’ve got a customized permalink structure.

Any thoughts?

Thanks in advance!