Hey blackyblackguy, let me first say that I don't have a Galaxy Nexus yet (coming in the mail tomorrow), but I think I can help you. Check your recording resolution setting. 1080p and 720p should get rid of those black bars, whereas 480p and lower resolutions will give you the black bars. Here is why you are seeing the black bars:
Whenever you see black bars horizontally, or vertically, it means the aspect ratio is not the same as the display. Because the Galaxy Nexus is 720p, which has pixel dimensions of 1280 pixels wide, by 720 pixels tall, the Galaxy Nexus has an aspect ratio of 16:9. This means for every 16 pixels wide, there are 9 pixels tall. You are most likely shooting in 480p, which has an aspect ratio of 4:3. You are seeing the black bars because whereas the vertical pixels are maxed out to the top of the screen, the video can't stretch the full width because of the aspect ratio it is limited to.
For common reference, HD screens are typically set to 16:9, whereas CRT screens are typically set to 4:3.