You can do it as often as you like, but if there's not a problem, you may slow done certain things until the cache gets rebuilt.
Technically true, but if you get into the "deep" cache cleaning that some utilities have as an option, there is actually some small chance of it screwing things up that were working properly (I had an old version of the [OS]CacheCleaner utility do this to me once). As LCC itself says, only do this if you're actually having problems, not as maintenance.
"Light" cache deletion, however, should be perfectly safe, and has at least some chance of helping with low storage space.
Another thing to check is if your system log file has gotten horribly bloated. It's uncommon, but misbehaving software will sometimes dump massive amounts of error messages into the logs, which can cause severe space shortages. Open up Console.app in your utilities folder, find System.log, select it, and check the size in the bottom left corner of the window. Alternately, most maintenance utilities have an option for deleting logs, which can be done safely without worry (they are, after all, just logs). Knowing if that was the problem is valuable, though, so you can do something about the root cause.
Recent real world example: Silverlight, when playing video off NBC's Olympics website, dumped hundreds of error messages into the logs every second. 750MB/hour worth. Either watch a few hours of full-event Olympics or forget to close the browser window for a day or two, and you've got tens of gigabytes worth of logs eating up your free space.