Congratulations! You've pushed Excel to it's limit. Yeah, we've all
hit that wall from time to time.
I had one application where I ended up importing my data into ACCESS,
then sorting it and doing some pre-work to get it down to below 65500
lines. I don't know if your data is flexible enough for that.
Otherwise, Excel 2007 is your next call.