Hello,
I'm going to trim some of this and do "middle posts" hope you don't mind.

...
> On 04/13/2011 06:32 AM, Andrew Elwell wrote:
...
>> # yum install openldap-servers
...
>> Dependencies Resolved
>>
>> =============================================================================
>>    Package                 Arch       Version          Repository        Size
>> =============================================================================
>> Installing:
>>    openldap-servers        x86_64     2.2.13-12.el4    sl-base           3.4 M
...

Yum should be getting openldap-servers version 2.2.13-12.el4_8.3
Do you not have your sl-security repo enabled?
If you don't, then you should enable it, and all this will clear up.

...
>> [root@vtb-generic-34 ~]# rpm -q openldap
>> openldap-2.2.13-12.el4_8.3.x86_64
...
>> and I can't do a straight upgrade:
>>
>> [root@vtb-generic-34 ~]# rpm -Uvh
>> http://linuxsoft.cern.ch/scientific/4x/x86_64/SL/RPMS/openldap-2.2.13-12.el4.x86_64.rpm
...
What you call and upgrade is really a downgrade.
You need to either get the updated version of openldap-servers,
http://linuxsoft.cern.ch/scientific/4x/x86_64/errata/SL/RPMS/openldap-servers-2.2.13-12.el4_8.3.x86_64.rpm
Or, if you are really determined to downgrade, then use the correct rpm 
option to downgrade.
Troy
-- 
__________________________________________________
Troy Dawson  [log in to unmask]  (630)840-6468
Fermilab  ComputingDivision/SCF/FEF/SLSMS Group
__________________________________________________