As of the release of Burp 1.3.5 the same methodology shown in a previous post video (using Android SSL enforced apps with Burp) is a bit different.
You still need to import Burp as a CA to Android (using keytool & BountyCastle tool) but Burp will generate certificates on the fly (correctly) so you no longer need to configure your own CA Cert in Burp for each App.
Also, if you are running Ubuntu its likely you have multiple versions of Java jvm running.
This affects the keytool, actually it affects the classpath location for the jar file "bcprov-jdk16-141.jar".
For instance, I had both:
/usr/lib/jvm/java-6-sun-220.127.116.11/ & /usr/lib/jvm/java-6-sun-18.104.22.168/
So a quick fix is to perform a
sudo apt-get remove sun-java6-bin sun-java6-jre sun-java6-jdk
sudo apt-get install sun-java6-bin sun-java6-jre sun-java6-jdk
Then move the bcprov-jdk16-141.jar file back into your newest jvm directory (as of now 22.214.171.124)