It was "Sandokan", and came from the same folks behind "Willy Fogg" and "Dogtanian". Like those two cartoons, it was based on a book/series of books that had already been filmed as live-action. The production company simply changed the human characters to animals. A Google search on "Sandokan cartoon" should get you some hits, or you could get some episodes on DVD:
http://www.sendit.com/video/item/7000000089480 (Sendit was the first place I found, and may not be the cheapest).