Addendum: Above solution works with beamer font size options 12pt, 11pt (default size) and 10 pt. With option 9pt compilation fail, since I haven't installed package extsize yet (I don't need it), which is necessary for fonts 8pt and 9pt. I assume, that your problem is caused by this package.
As stated in manual (pp 159), fonts 8pt and 9pt are to small (so they haven't native beamer support), and "If you really need to fit more onto each frame, use 10pt option (which works without extsize)".
Solution: See, if you can stick with 10pt. Benefits: (i) nicer and more clear presentation as at font size 9pt and (ii) you have solved your problem.