I have a very similar (or possibly the same) problem trying to calculate sales territories. I simply have too many territories. I have 26 territores to calculate based on state and zip.

One thing you can try is using the CONTAINS function, to see if that helps shorten your formula to under 1000 characters (unfortunately, this didn't help me, the formula was still to big). Another thing to note is that Winter '06 allows for CONTAINS to be used in combination with ISPICKVAL. Looking at the sample you provided, I believe you could use this new functionality to reduce your formula by a few more characters.

Here's an example of using the CONTAINS function for calculating a sales territory by state. Unfortunately for me, this is an incomplete formula (CA, NV, TX, NY, and PA don't appear in my formula because I have to calculate the sales territory in those states based on zip, and that makes the formula too long).

IF({!State}="","Null",
IF(CONTAINS("AK:MT:OR:ID:WA",{!State}),"Northwest",
IF(CONTAINS("AZ:NM",{!State}),"Southwest",
IF(CONTAINS("UT:WY:CO:NE",{!State}),"Mountain",
IF(CONTAINS("ND:SD:MN:IA",{!State}),"Upper Midwest",
IF(CONTAINS("KS:MO:OK:AR",{!State}),"Midwest",
IF(CONTAINS("AL:GA:SC",{!State}),"South",
IF(CONTAINS("FL:PR:VI",{!State}),"Florida",
IF(CONTAINS("WI:IL",{!State}),"IL/WI",
IF(CONTAINS("MI",{!State}),"Michigan",
IF(CONTAINS("OH:IN",{!State}),"OH/IN",
IF(CONTAINS("KY:TN:NC",{!State}),"KY/TN/NC",
IF(CONTAINS("VA:WV:DE:MD:DC",{!State}),"Mid-Atlantic",
IF(CONTAINS("ME",{!State}),"Maine (ICBS)",
IF(CONTAINS("CT",{!State}),"CT",
IF(CONTAINS("HI",{!State}),"Hawaii",
IF(CONTAINS("LA:MS",{!State}),"Gulf States",
IF(CONTAINS("NJ",{!State}),"NJ/East PA",
IF(CONTAINS("MA:NH:RI:VT",{!State}),"New England",
"Need to Use Zip for Territory Calc"
)))))))))))))))))))


If this doesn't help you, keep your eye on the thread I just created (link below). Let's hope someone else has a great sugggestion!
http://forums.sforce.com/sforce/board/message?board.id=general_development&message.id=5962