My little guy is 2.5 and he is puzzle-crazy, too! For Christmas, he got a bin that had 10 puzzles with 48-100 pieces. He mastered the 48-piece puzzles within two weeks, but he does not have the attention span to finish the 100-piece puzzles yet. The pieces are quite small, so that may have something to do with it. It is difficult to find puzzles that are challenging enough for DS but are of subjects that are interesting for him. He does not want to do 50-piece puzzles of floral landscapes!
The best ones I can find right now are the giant floor puzzles. We have three with 50+ pieces and he LOVES them. He has one block puzzle of barnyard animals (12 blocks) and he has ignored it for the past three months. Only this past week has he figured out how to do it and he has been doing it non-stop.