Hi Thillo, 
Sweet.. So it's something in the coffee 

 Higher acidity does not mean better staining obviously. 
I always wondered on what exactly happened chemically we when stain a blade and what is the main substance, but I never ventured into finding the answer. 
G'day Alan,
Do you have any suggestions of other solution that can be used to stain wootz? I have some difficulty in finding FeCL3 here in Malaysia. I am considering of using coffee now.