Ok, version 3.2.1.1 is up. We have made 2 changes you might want to try:
1. Unity now decides what video codec to use for Android2. Added option to disable the videos in the settings menu. Try this if the solution above doesn't work.