Since no one has yet replied to your post, the following might, at least, show you that others are seeing the same thing that you do. I'm running Visual Fortran Composer XE 2011 SP1 with Visual Studio 2010 using Windows 7 64-bit on a machine with the i7 Core 860 and 8 Gb RAM.
For random double precision matrices, all eigenvalues and all eigenvectors, times are: (averages for 3 runs)
2111 X 2111 matrix; Syevd 2.4 secs, Syevr 2.5 secs
5103 X 5103 matrix; Syevd 28.5 secs, Syevr 28.5 secs
10003 X 10003 matrix; Syevd 207 secs, Syevr 197 secs
It may be worth noting that tridiagonalization, using Sytrd+Orgtr, takes 1.5 secs for the 2111x2111, 22.4 secs for the 5103x5103, and 165 secs for the 10003x10003 random matrices. Also, the eigenvectors obtained from Syevd are the same, to ~1.0D-11, as those from Syevr.
I get essentially the same times, within ~10%, when I use these routines in a C# 'wrapper'.
My own parallel implementations, from scratch, of the MRRR algorithm runs more than twice as fast as my own implementation of the 'Divide and Conquer' algorithm. Both of those, and my own implementation of tridiagonalization, are, at best, a factor of 3 SLOWER than the corresponding MKL routines.
I too find it surprising that Syevd is as fast as Syevr ... but, with performance like that, I'm not complaining!
The Relatively Robust Representations algorithm has shortages: low accuracy of eigenvectors, the big association of a velocity of algorithm on matrix structure, possible malfunctions in work. See also: http://software.intel.com/en-us/forums/showthread.php?t=73653&o=d&s=lr