2560x1600 on Dell U3011 with new MacBook Pro
Try using the mini Display Port to the Dell's Display Port.
That's how I connect to 2 2560*1440 Dell screens.  

I've found, in order of reliability  


Display Port - works every time  
DVI - works most of the time, can be fussy on some screens  
HDMI - haven't used  
anything  > VGA [barely works at all on anything over 1920*1200]