GTX 580 is a pointless recommendation - it is a waste of money compared to the 7950 right now. The 7950 is newer, cheaper, faster, and can overclock somewhere between 20-50% depending on the card, putting the GTX 580 to shame.
As for maxing crysis, I believe a GTX 570 will do it at 1080p with 4xAA as long as you don't expect amazing framerates. I think it's probably the bare minimum to get something close to playable. I would recommend, however, a 7950 or 7970.
My rig averages about 52 fps during Crysis & Crysis Warhead - 1080p maxed settings with 4xAA.
do you have your xfx black edition overclocked any