No, this is not normal but I've had a similar problem occasionally with my Altec Lansing iMT525 Bluetooth Speakers. Something similar in concept to Sri's answer almost always works for me, and I need to do it only once per connect.
Auto-switching Bluetooth profiles to re-initialize PulseAudio
If you're looking for a culprit, I'd look at Ubuntu's sound system, PulseAudio first, and then your bluetooth receiver. Try this:
First, delete and re-pair your Bluetooth device.
Then, copy and paste the below into a .sh file in your home directory, say /home/brillout/pabluezswitch.sh:
#!/bin/bash
BLUEZCARD=`pactl list cards short | egrep -o bluez.*[[:space:]]`
pactl set-card-profile $BLUEZCARD a2dp
pactl set-card-profile $BLUEZCARD hsp
pactl set-card-profile $BLUEZCARD a2dp
Make the file executable by opening a terminal and typing chmod +x ~/pabluezswitch.sh
Go to Settings...Keyboard...Shortcuts, and create a custom shortcut; name it whatever you want, with the command as /home/brillout/pabluezswitch.sh (substitute appropriate username in path!). Click Apply, and then click on the right where it says Disabled to set up a keyboard shortcut to execute the script.
What this does is force the PulseAudio system to resynchronize the audio being sent to your headset/speakers by switching profiles from ad2p -> hsp -> a2dp, thus hopefully getting rid of any latency.
Whenever you connect and notice the lag, you should press the keyboard shortcut chosen above to attempt to fix the latency -- hopefully it works for you!
mplayer, you do so by pressing the+and-keys. In VLC, I don't know how to set the delay, but I'd be surprised if VLC doesn't have such an option. – leemes Jun 3 '12 at 14:29Tools->Track Synchronisation, or play with the--audio-desyncoption. I'm afraid I'm not sure what the units are, and which direction is positive, and the help is not forthcoming on the matter, but that's where you want to look. – Darael Jul 31 '12 at 19:32