It looks like the newest Ubuntu 12.04 breaks the Brother QL-500 printer driver.
After a lot of fiddling, including trying to use Brother's official driver, I found a solution.
Based on this forum post I edited /etc/cups/ppd/QL-500.ppd, changing "rastertoptch" to "/usr/lib/x86_64-linux-gnu/cups/filter/rastertoptch". This is slightly different to the change in the forum post, but it is the same idea.
Update: it appears that a recent update has moved rastertoptch to /usr/lib/cups/filter/rastertoptch
