Platform:

• uname -a -> Linux LenovoE330 3.16.0-4-amd64 #1 SMP Debian 3.16.7-ckt25-2 (2016-04-08) x86_64 GNU/Linux
• dpkg -l '*matplotlib*' -> python-matplotlib 1.4.2-3.1 amd64, python-matplotlib-data 1.4.2-3.1
  • dpkg -l 'python' -> ii python 2.7.11-2 amd64
  • Everthing installed using sudo apt-get install -t sid pyhton python-matplotlib

This short example:

from matplotlib.pyplot import *
subplot( 111, title=r"$\mathcal{O}\left( N^3 \right)$" )
show()

renders to (cropped only title):

But it should render to:

The latter was created by manually changing the example to:

from matplotlib.pyplot import *
matplotlib.rc('text', usetex=True)
subplot( 111, title=r"$\mathcal{O}\left( N^3 \right)$" )
show()

Therefore it seems that the problem is only with the internal mathtext rendering, not with LaTeX per se.
The problem also disappears when using N^\mathregular{3} and \mathbb{3}, but reappears when using N^\mathit{3} or N^\mathrm{3}.

See also https://stackoverflow.com/questions/14733605/python-matplotlib-label-title-wrong-character