Are your statistics up to date? Are they the correct statistics?

It's not unheard of to have some queries go "bad" after an upgrade because the appropriate statistics have not been gathered. Having all queries go bad is a new one to me...