Something like 8 sprites per scanline or bad stuff happens?
Yup. You'll get a lot of slowdown if you have more sprites per scanline. Most of the time people fixed this by flickering sprites on and off, but it's godawful to look at. MegaMan 6, while having gorgeous sprites and tiles, has this problem a lot.
This is also why you see big boss fights on NES on black backgrounds most of the time, by the way. It frees up an extra color (black, since you can just place transparency where you want black) and you don't have any other sprites on screen that you have to account for, so you can make your boss nice and big.
By the way, Ben_Hurr, I don't agree with others in this thread that you should just stick with 32x32 because you're good at it. Trying new things, especially smaller things, is great for improving your technique. Making small sprites teaches you the importance of every single pixel much, much more than doing larger sprites.
@rdein: Offtopic, but can you get rid of the glitch thing in your name? It's cool and all, but makes for awful quoting as you can see in the post above me