Did you do the research on magic after initially talking to Rinny about learning it? If not, go to the library in the succubus tower and look around. Once that is done you should be able to get Rinny to teach you.
