To fix this:
Go to "My Documents" > "StarCraft II Beta" > open the "variables.txt".
Search for width=1280 and replace this with (or just add these 2 lines if width=x does not exist in your variables.txt):
width=1360
height=768
Note that this is 1360, not 1366. This is most likely because the game only supports true 16 : 9 resolutions and 1366x768 is a bit off. When you start SC2 again you'll notice a minor graphical glitch at the top and bottom bars of the opening menu; they are cut off on the sides because the graphics in SC2 only go up to 1280 or whatever.
You can now play on full screen without having the black side bars
