I think there might be something to the leveling bit. I've seen several times where i have pretty good skill gains right after I gain a level. I wonder if each consecutive skill gain gets less likely while at the same level or if you have x number of skill gains before the difficulty goes up and all of that resets when you level.

Just seems to be a pattern. Or it could just be that the higher your level the easier it is to learn skills.