Okay, just managed to fix this myself. What I did was go into the Catalyst Control Manager then Desktop Management > Desktop Properties and change the resolution to something non-native. I then went to My Built-In Displays > Properties (Built-In Display) and selected the "Full" option rather than the "Aspect Ratio" option.
After this, I went back to Desktop Management > Desktop Properties and changed the resolution back to its native resolution. I then booted up Starcraft and it filled the screen!
Good luck to anyone with the same problem!