I changed the way automatic conversions and deconversions work a while ago, and I think I may have been a little overzealous in some areas. It's something I've been meaning to revisit for a while now, but haven't had chance.
So while I can't speak to specific issues without seeing them in action (it's possible you've also found a separate bug in the way followers are calculated), I'd say that it qualifies as a quasi-bug 
I will try and see if I have some time to look into it in the near future.
Did you change preaching? Machiavel has 100 oratory fame, and yet, more often then not, 12 hours converts no more than 50 people in a typical region, 150 in a large city.
