Nick, the trustworthiness is in your appearance as a whole. Who would look at Patrick Stewart and think he's a shady skinhead? If you dress neat and clean and your bearing shows self-respect and humility, you'll come across as trustworthy.
My wife is enjoying my bald appearance even though she was doubtful at first. In fact, tonight she said I look sexy. So there you have it!
It'll be a big adjustment for anyone who's known you for any length of time, but it needs to be about what works best with your features and what makes you feel best about yourself.