Debit/check cards are a different breed of Visa. It's weird. Mine does build my credit, though. And I like Wachovia, they have waived $130 in overdraft fees from me so far ($37 for a 10 cent overdraft, rediculous), but that might just be because the guy who handles that likes me 
Anyway, debit cards do affect credit ratings.
It affected your credit because you were overdrawn. Doing that to a checking account affects your credit. That's why you can't get one without a cosigner until you're an adult.
My checking account has had no effect on my credit at all, the only reason I have good credit is because of my loan. And like you were saying, the Visa Check Card ( which I also have, in addition to my actual debit card ) doesn't build credit either.
If you go to your bank and tell them you want to apply for a loan, and then ask them if they can report your checking account history to the credit bureau, it will have a modest, positive affect for your credit. A checking account isn't that special, but I guarantee you, it affects your credit in the long term.
By the way, it might not have affected yours too terribly much because
you're only 19.
