Does this have something to do with perineal irritation from your bike saddle, given that it does not occur when running?

It is my understanding that bladder training does not actually increase bladder capacity, but just lets you know how long you can put up with the misery until the inevitable happens.

As to caffeine, it is a weak diuretic and can directly stimulate the bladder - is it worth trying decaffeinated tea/coffee, if you have not already done so?