Frankly speaking I have never heard that exchanging links is a black hat seo... Expecially if I exchange links ONLY with related sites.
I have link exchanges like this on many other websites (more than 30) and they all are ranking very well. So, I think the problem have to be found elswhere