Its either an issue with the smtp server settings or you have port 25 blocked on a firewall. Make sure you have no software running that could block internet traffic. Try deleting and re-adding your gmail account in mail.
EDIT: just noticed gmail uses SSL, so the port would be 465. Either way, turn off any internet protection software or similar and add the account again.