I have same problem. After updating to 1196 my wallet doesnt send automatic tithes regularly, although I have coins with requested coin age and amount. I tried to change tithe= parameter, but its same.

Second issue I dont like - if my wallet finally sends some tithes - they often ends as illegal.

When I tithe manually sometimes I get this error:

tithe 9
{
  "Error": "Error: The transaction was rejected! This might happen if some of the coins in your wallet were already spent, such as if you used a copy of wallet.dat and coins were spent in the copy but not marked as spent here."
}