That is an option on the account in pidgin.
Accounts->[Your account]->Edit Account
If the option is enabled and still isn't working then you need to tell us
which protocol this is for and ideally get the Help->Debug Window output
from when you receive a new email to see if anything interesting is
reported there.
-Etan