I've seen similar issue in RF 3.3.1 or 3.3.2 (sorry, but don't remember version for sure). Can you please try with 3.3.3?
I tried using RichFaces 3.3.3. But no help. I am still getting gap between the combo box component and validation message. any help will be appriciated.