How did you install calibre? Did you install it though Ubuntu's software repository? I'm thinking you did and the Ubuntu packagers have a bad habit of breaking calibre (as well as other apps) by never testing or using any help they've been offered from upstream. Almost every Ubuntu version has shipped with calibre broken...
pyPDF is used and the bundled version that has some changes to upstream is not being used in your conversion. Install using the binary installer from
http://calibre-ebook.com and you will be fine.