well, personally i have not reached that part of the game yet (still a mercenary jumping around factions)
but i believe the brytenwalda uses the diplomacy mod for all that stuff and if so, what's happening is that your trainer is indeed training your troops, i.e. he is giving them experience. But recruits are higher level in this mod (15 as opposed to 1 in native) so it will take longer to get the required xp for 2nd tier troops. (ive heard of putting a companion in there as a trainer, have you tried that?)
as for your recruiter, he probably got defeated. what happens when you order recruits brought to your town is a 1 man unit (titles 'recuiter') Runs from town to town picking up fresh soldiers for your garrison. But bandits are more dangerous (and MUCH faster at least it seems to me) in this mod, so he probably got caught by a bandit group or enemy lord and defeated. (which should of brought up a message in red on the bottom left corner that said 'your recruiter commissioned to recruit x amount of men has been defeated')
if this happens you lose your money and get no recruits.
Id say stay away form that feature in this game, its too much risk and its much easier to get all the recruits you need yourself. Just put spies in the villages closest to your town. You'll get your rep with them to 22 in about 10 days and this will allow 30-40 men per recruitment per village. more than enough to get the soldiers you need.