If I have an SSL certificate for my mail server, will it mean that I am less likely to have my mail put into a spam box?
Currently, I am using a self-signed certificate for the server, but some of my users have complained that email they are sending often gets ranked as spam... is this connected?
No, an SSL certificate for your mail server won't make a difference. Look into DKIM, DomainKeys, and SPF records, check that you aren't on blacklists, etc. The content of your e-mail makes a big difference, too. There's a lot to ensuring e-mail delivery.