If nitrate is as low as that and the tank is planted maybe try testing for phosphate? I'v never tested my tanks for it, but I have read that high levels can cause problem algae.
If phosphate is low as well there's only really lighting left to consider, If day length is overly long and/or the lighting is too dim some types of algae can still grow. I used to have problems with a black hair like algae in my 35g, but since I've swapped from fluorescent to a very bright LED fixture it's almost completely gone.
Hope this helps, I'm out of ideas now!
Edit: Just a thought, you could try testing your tap water for nitrate, here in the UK certain areas sometimes have nitrate present . It might be that you're adding nitrate every time you do a water change?