Selecting from outliner doesn't show the problem. And using 'A' to deselect seems OK.

This sounds like a graphics card/driver related issue, please attach details about that (Help menu > System Info in Blender). If you have ATI/NVidia card, generic advice is to install latest driver from the manufacturer website. A workaround is also to run with software opengl, there's a blender-softwaregl command included in official releases.

You are right, softwaregl shows no problem.

Here is my build system info.
============================================
= Blender 2.61 (sub 0) System Information =
============================================


Blender:
============================================

version 2.61 (sub 0), revision 42700. Debug
build date: 2011-12-18, 13:00:06
platform: Linux
binary path: /mnt/svn/blender/build/bin/blender
build cflags: -fopenmp -msse2 -msse -pipe -fPIC -funsigned-char -fno-strict-aliasing -Wall -Wcast-align -Werror=declaration-after-statement -Werror=implicit-function-declaration -Werror=return-type -Wstrict-prototypes -Wno-char-subscripts -Wno-unknown-pragmas -Wpointer-arith -Wunused-parameter -Wwrite-strings -Wno-error=unused-but-set-variable
build cxxflags: -fopenmp -msse2 -msse -pipe -fPIC -funsigned-char -fno-strict-aliasing -Wall -Wno-invalid-offsetof -Wno-sign-compare
build linkflags: -pthread
build system: CMake

Python:
============================================

version: 3.2.2rc1 (default, Aug 14 2011, 18:50:27)
[GCC 4.6.1]
paths:
/mnt/svn/blender/build/bin/2.61/scripts/addons_contrib
/mnt/svn/blender/build/bin/2.61/scripts/addons
/mnt/svn/blender/build/bin/2.61/scripts/startup
/mnt/svn/blender/build/bin/2.61/scripts/modules
/mnt/svn/blender/build/bin/2.61/python/lib/python3.2/
/mnt/svn/blender/build/bin/2.61/python/lib/python3.2/plat-linux2
/mnt/svn/blender/build/bin/2.61/python/lib/python3.2/lib-dynload
/mnt/svn/blender/build/bin/2.61/scripts/addons/modules

Directories:
============================================

scripts: ['/mnt/svn/blender/build/bin/2.61/scripts']
user scripts: None
datafiles: /home/ruan/.blender/2.61/datafiles/
config: /home/ruan/.blender/2.61/config/
scripts : /home/ruan/.blender/2.61/scripts/
autosave: /home/ruan/.blender/2.61/autosave/
tempdir: /tmp/

OpenGL
============================================

renderer: Gallium 0.4 on AMD RV620
vendor: X.Org
version: 2.1 Mesa 7.11.1
extensions:
GL_ARB_multisample GL_EXT_abgr GL_EXT_bgra GL_EXT_blend_color
GL_EXT_blend_logic_op GL_EXT_blend_minmax GL_EXT_blend_subtract
GL_EXT_copy_texture GL_EXT_polygon_offset GL_EXT_subtexture
GL_EXT_texture_object GL_EXT_vertex_array GL_EXT_compiled_vertex_array
GL_EXT_texture GL_EXT_texture3D GL_IBM_rasterpos_clip
GL_ARB_point_parameters GL_EXT_draw_range_elements
GL_EXT_packed_pixels GL_EXT_point_parameters GL_EXT_rescale_normal
GL_EXT_separate_specular_color GL_EXT_texture_edge_clamp
GL_SGIS_generate_mipmap GL_SGIS_texture_border_clamp
GL_SGIS_texture_edge_clamp GL_SGIS_texture_lod GL_ARB_framebuffer_sRGB
GL_ARB_multitexture GL_EXT_framebuffer_sRGB
GL_IBM_multimode_draw_arrays GL_IBM_texture_mirrored_repeat
GL_ARB_texture_cube_map GL_ARB_texture_env_add GL_ARB_transpose_matrix
GL_EXT_blend_func_separate GL_EXT_fog_coord GL_EXT_multi_draw_arrays
GL_EXT_secondary_color GL_EXT_texture_env_add
GL_EXT_texture_filter_anisotropic GL_EXT_texture_lod_bias
GL_INGR_blend_func_separate GL_NV_blend_square
GL_NV_light_max_exponent GL_NV_texgen_reflection
GL_NV_texture_env_combine4 GL_SUN_multi_draw_arrays
GL_ARB_texture_border_clamp GL_ARB_texture_compression
GL_EXT_framebuffer_object GL_EXT_texture_env_dot3 GL_MESA_window_pos
GL_NV_packed_depth_stencil GL_NV_texture_rectangle
GL_ARB_depth_texture GL_ARB_occlusion_query GL_ARB_shadow
GL_ARB_texture_env_combine GL_ARB_texture_env_crossbar
GL_ARB_texture_env_dot3 GL_ARB_texture_mirrored_repeat
GL_ARB_window_pos GL_EXT_stencil_two_side GL_EXT_texture_cube_map
GL_NV_depth_clamp GL_APPLE_packed_pixels GL_APPLE_vertex_array_object
GL_ARB_draw_buffers GL_ARB_fragment_program GL_ARB_fragment_shader
GL_ARB_shader_objects GL_ARB_vertex_program GL_ARB_vertex_shader
GL_ATI_draw_buffers GL_ATI_texture_env_combine3 GL_ATI_texture_float
GL_EXT_shadow_funcs GL_EXT_stencil_wrap GL_MESA_pack_invert
GL_ARB_depth_clamp GL_ARB_fragment_program_shadow
GL_ARB_half_float_pixel GL_ARB_occlusion_query2 GL_ARB_point_sprite
GL_ARB_shading_language_100 GL_ARB_sync
GL_ARB_texture_non_power_of_two GL_ARB_vertex_buffer_object
GL_ATI_blend_equation_separate GL_EXT_blend_equation_separate
GL_OES_read_format GL_ARB_color_buffer_float
GL_ARB_pixel_buffer_object GL_ARB_texture_compression_rgtc
GL_ARB_texture_float GL_ARB_texture_rectangle
GL_ATI_texture_compression_3dc GL_EXT_packed_float
GL_EXT_pixel_buffer_object GL_EXT_texture_compression_rgtc
GL_EXT_texture_mirror_clamp GL_EXT_texture_rectangle
GL_EXT_texture_sRGB GL_EXT_texture_shared_exponent
GL_ARB_framebuffer_object GL_EXT_framebuffer_blit
GL_EXT_framebuffer_multisample GL_EXT_packed_depth_stencil
GL_ARB_vertex_array_object GL_ATI_separate_stencil
GL_ATI_texture_mirror_once GL_EXT_draw_buffers2
GL_EXT_gpu_program_parameters GL_EXT_texture_compression_latc
GL_EXT_texture_env_combine GL_EXT_texture_sRGB_decode
GL_EXT_timer_query GL_OES_EGL_image GL_ARB_copy_buffer
GL_ARB_half_float_vertex GL_ARB_instanced_arrays
GL_ARB_map_buffer_range GL_ARB_texture_rg GL_ARB_texture_swizzle
GL_ARB_vertex_array_bgra GL_EXT_separate_shader_objects
GL_EXT_texture_swizzle GL_EXT_vertex_array_bgra
GL_NV_conditional_render GL_AMD_draw_buffers_blend
GL_AMD_shader_stencil_export GL_ARB_draw_buffers_blend
GL_ARB_draw_elements_base_vertex GL_ARB_explicit_attrib_location
GL_ARB_fragment_coord_conventions GL_ARB_provoking_vertex
GL_ARB_sampler_objects GL_ARB_seamless_cube_map
GL_ARB_shader_stencil_export GL_ARB_shader_texture_lod
GL_EXT_provoking_vertex GL_EXT_texture_snorm
GL_MESA_texture_signed_rgba GL_NV_texture_barrier GL_ARB_robustness

Moved from Blender 2.5 Bug Tracker to OpenGL errors

This is indeed driver issue. Not much we can do in this case, you might check for drivers update or report to guys developing gallium. Moving to open gl bug tracker.