Yoshi's Story uses sprites, so does the aforementioned Mario Kart 64. They're just taken from pre-rendered images (like the Donkey Kong Country games) so they look a little different. But they are indeed 2D sprites. Then of course there's Paper Mario, which is almost nothing but sprites.
I believe the problem with the N64 is something about how it doesn't have a dedicated 2D processor or doesn't process 2D images well for one reason or another. I think the sprites are actually just a single large, flat polygon, and so the detail suffers a bit from having to do that.