This probably means that emacs isn't taking full space inside gnome-terminal.
Probably not. It could happen even when emacs takes full space due to the background color rendering of fringes. For example, you have the same problem on the right side also. Moreover, on the right side this blue fringe becomes thicker below the mode line. All this points to font and line sizes resulting in fractional multiples of the screen size. Emacs is taking the full space but rendering in different colors.
linum-mode and mode-line themes often cause this. Besides turning off
linum-mode, try tweaking font metrics as others have suggested above. Or play with fringe theme colors. Make them same as the main theme's background color. Some themes come with a variable for such tweaking. For example:
(setq solarized-distinct-fringe-background t)
You'll have to find equivalent variables in your active theme.