Navagon: If any character needed a total rewrite it is Superman. It's the only way the character is in any way tolerable ... Albeit not so much to me as his only weakness is the fact that everyone and their grandmother has some kryptonite.
Superman has had multiple rewrites; each time his powers get reset back to a more sensible level, but as the run goes on the writers want to put him in increasingly epic situations by throwing bigger and bigger villains at him (especially if they want the series climax to involve saving all of reality or whatever) so end up sequentially bumping his powers right back up to ludicrous levels (including "breathing" in space by holding his breath indefinitely).
Superman getting increasingly powerful is inevitable because he's a star player, and at this point it's unlikely that they would change his power set to give him additional weaknesses. Superman is also weak against magic, but the problem is that this doesn't come up much because he doesn't have any well-known magical foes (even Batman has a wizard or two). More often than not they end up putting him up against Captain Marvel for this purpose, but since both are heroes they can't have them fight each other on a regular basis without it becoming ridiculous. His general power creep can also lead to him developing some level of resistance to magic (and sometimes kryptonite as well) which further reduces the effectiveness of magic-based foes.