The higher the resolution the more pixels that have to be pushed out and thus a higher transmission rate down the cable, (if you're intending to keep the same refresh rates).
The construction/quality of the cable is a major
factor in whether it will work at a higher frequency, eg. thinner conductors or high percentage of contaminants in the materials will cause greater attenuation at higher frequencies.
If where you bought it, specified that it supported 2560x1600, (as this one
does), and it didn't work then you'd be fully justified in getting a refund/replacement.
Here's a company
in the UK advertising 3 and
5 meter cables that will work up to 2560x1600. They're also available in a 25 meter length if you want to put the monitor next door.EDIT:
Just realised, make sure you get a DVI-D Dual Link
cable. DVI-D Single Link is restricted to 1920x1200.