(updated with new information) Calculation of the transaction fee when "paytxfee" is set has changed, without announcement or documentation.
Per @sipa :
In earlier versions however the size of a transaction was rounded up to a multiple of 1000, as that is how the mining code used to sort transaction years ago. In 0.12, it was finally changed to the accurate formula that works at an accuracy per byte. If the paytxfee value was always exactly what you saw as resulting fee, that must mean all your transactions were 1 kB in size.
In bitcoin.conf, I had
paytxfee=0.0001
In 0.11, that meant that BTC 0.0001 would be added to every outbound tx as a fee.
in 0.12, it means every tx will have added to it a fee of BTC 0.0001 per kilobyte
This is not documented in the release notes. As a result of this, I've got 3 days worth of spend transactions caught in unconfirmed limbo, having gone out with fees like 0.00002260 instead of 0.0001.