Sorry JP, but your info is out of date - the LZW patent expired some time ago.
Also, software patents in general are a strange quirk of American law and so European software developers are unaffected by them. Hence there have always been plenty of tools around to read and write GIF files.
Anyway, the best tool for the job is probably ImageMagick - it should be available as a standard package for just about any distro and provides the powerful 'convert' command. Try 'man convert' for more info.
You may also want to check out the netpbm/pbmplus packages which convert all sorts of image types.