Your design should fit going from the 9500 to the 9500xl. The 9500xl actually has more function block fanin (36 to 54!) so I would think that there should be no fitting issues. The only architectural features lost are macrocell feedback and wire-anding in the AIM. The loss of macrocell feedback should be made up for by the additional FB inputs. The loss of wire-anding would cause your PTerm requirements to increase. Perhaps if you were near the maximum utilization for this it would not fit.
You may want to try contacting the Xilinx hotline. They are willing to try fitting close designs.
Arthur