Animated GIF support was added to gd 2.0.29. See its web page for the details. It sounds like the original poster knows what he needs to do but isn't getting the right results. He provided no code however (but isn't even using Perl, so no matter).

As for the patent, Boutell says: "The well-known patents on LZW compression held by Unisys have expired in all countries. British Telecom and IBM may hold related patents but have never chosen to require royalties for GIF applications, to the best of my knowledge. I am not a lawyer and cannot give legal advice regarding this issue."