Central Admin shows our max upload size to be 90 megs, but trials of even text files at 35 megabtyes won't upload. Smaller files are fine.
Where should we look now?
It could be a number of things. The following article outlines most of the usual causes: Configuring Large File Support
What sort of error are you receiving? Not sure where in CA you're looking but you'll want to check the application management section of your particular web app.
If I remember correctly you need to change the size in MOSS as well as in IIS.
Have a look at this article.