Maybe they've switched on
SMTP authentication ?
i.e. where you need to log-on to your SMTP server in order to be able to send outgoing messages.
Can't think of anything else. Don't think it's an account-specific issue on their server, it's more likely to be their server mail program (Exim or whatever they use) if it's not the above.
hth
Charles