The problem is that the cloak is too weak right now. Unfortunately, many of the things people are asking for would take it to the other extreme and make it far too strong.
Here's my two slips of gold-pressed latinum:
1. Probes should have a very weak chance of detecting a cloaked ship. After all, they have a long range, and they move quickly. Perhaps if a probe detects a cloaked ship, it could then track the ship until the probe burns out (obviously, the cloaked ship will know if a probe is following it). In this case, a probe should have an unaltered chance of detecting a cloaked ship, like 1 in 10 (or even less). A probe is automated, and should be unaffected by officer skills, and even computer level.
2. All computers should have a chance of detecting a cloaked ship, with the lowest having a pathetically poor chance, but still a chance, nonetheless. This way that little frigate with the legendary Ops officer still has a tiny chance of detecting a cloaked ship.
3. Cloaking/decloaking times should be altered. Four seconds, as one person said, is a bit long. But let's put a little racial flavor here. Klingons use the cloak to enter battle, but once in battle, they are rarely willing to leave, so, perhaps a one second decloak with a three second cloak for Klingons. Romulans are more likely to sneak away after their attack, so perhaps a one second cloak and three second decloak for Romulans (or, since Romulans are the masters of cloaking technology, maybe even a two second cloak and two second decloak).
The last thing I want to see is Taldren take the Funcom approach to "fixing" a problem by overdoing it, and then making a second patch to actually balance it like it should have been done with the first patch.
It won't really take much to make the cloak a very useful piece of technology. Just fix the various cloak bugs that currently exist, and slightly (SLIGHTLY) improve the cloak itself.