What steps will reproduce the problem?
1. Press <ESC> (Very important, not only for leaving any mode)
2. Press <SHIFT> + O
The time between 1. and 2. needs to be short enough.

What is the expected output? What do you see instead?
If, instead of pressing <SHIFT> + O, we press just O, the response is very 
quick as expected. Weirdly, with <SHIFT> + O the response is very slow to come. 
Sometimes, it even print a 'O' and then change its mind end do what's expected 
(i.e. open a line before the current one in INSERT mode)

What version of the product are you using? On what operating system?
VIM - Vi IMproved 7.3 (2010 Aug 15, compiled Mar 24 2011 07:10:07)