Umm, works for me? As a reference, I'm running Vim v7.4 patch 335. (it's not bleeding much!!)
I added the following two lines to my .vimrc:
highlight ColorColumn ctermbg=magenta guibg=Magenta
call matchadd('ColorColumn', '\%81v', 100)
Reloaded vim and taa-daa! The characters at the 81st position were magically magenta-ized.
EDIT:
As per the comments below, we discovered that @isxek needed to put these two lines LAST in their .vimrc file. Evidently, the colorscheme used (Molokai) sets the ColorColumn highlight scheme. I didn't see this issue since I set the ColorColumn highlight AFTER everything's loaded, essentially performing the same thing as 'putting the lines last'.
Personally, I'd recommend using a unique Group identifier so you don't mess with the highlight colors set for the actual ColorColumn highlighting group.
highlight MyLineTooLongMarker ctermbg=magenta guibg=Magenta
call matchadd('MyLineTooLongMarker', '\%81v', 100)
Works for both vim and gvim.
Have you tried/Do you use ColorColumn? Relatively new option in Vim to highlight a column (or columns!) based on textwidth. Was added with version 7.3. Very handy!
I use it thusly:
" it didn't exist before Vim v7.3, sometimes I encounter older versions of vim (centOS, looking at you!!)
if v:version >= 703
" a faint grey (gray?) color, not too insistent
highlight ColorColumn term=reverse ctermbg=233 guibg=#202020
" put the marker(s) at 'textwidth+2' (and at position 120)
set colorcolumn=+2,120
" if we're called as '*view', or on a console, turn off the colorcolumn
if v:progname =~? 'view' || &term =~? 'linux|console'
set colorcolumn=
endif
endif
So I essentially have two lines on my display, shown at textwidth + 2 and at position 120, as my default. I've grabbed a screenshot and moved the lines with set colorcolumn=+2,90 so it isn't too wide for here. Looks like this:

You can see the two vertical grey lines, positioned at textwidth + 2, and at position 90. Here, my textwidth was set to 78, so the lines are positioned at 80, and 90 characters out.
Now, you COULD use the two lines you've got to add a form of colorcolumn for a pre-v7.3 version of vim. Stick them in an else clause of the version check block above.