It is clear that animals do solve problems. What is less clear is the extent to which they are simply following some genetic program as opposed to engaging in reasoning and planning. Much research has focused on our primate cousins, especially the common chimpanzee, which is more closely related to humans than any other creature. The following videos are of chimpanzee problem solving:
The clip above is from a National Geographic programme Ape Genius (the entire programme is at this link).
In recent years, some researchers have become interested in the problem solving ability of birds, in particular the New Caledonian Crow. One such group is the Behavioural Ecology Group at Oxford University. A number of movie clips are available. The following clip shows a crow called Betty bending a wire in order to hook a bucket containing food that has been placed at the bottom of a tube: