The difficulty curve is slightly raised at the beginning of the game. (At first, Falkner's team never broke into double-digits, now there's a lv. 13 Pidgeotto...)
This new curve may be part of the reason. Also, Pokemon develop at different rates, and have different EXP rates. For example, at first, Training a Mawile is WAAAAY easier than training a Nincada, but eventually becomes easier at around Lv. 55.
This is just my thought, because I had the same issues at first. Take a look at your Pokemon's type, EXP base, etc, and experiment with different Pokemon to train on.