Hi Amanda
How many 301 redirects do you have on your old site? From what you have said it sounds like just one. Is that correct of have I misunderstood something?
If you have pattern-matched all the URLs from your old site to your new site and if those URLs don't exist on your new site, then a 404 is exactly what you will get.
A single pattern-matched redirect will only work if the relative path on the new site to pages is the same relative path that it was on the old site. So if you have the following:
oldsite.com/big-widgets.html
oldsite.com/little-widgets.html
etc
and you just create a single 301 redirect that says all the pages on oldsite.com have now moved to newsite.com, then the URLs on the new site will be expected to be found at the same relative paths as follows:
newsite.com/big-widgets.html
newsite.com/little-widgets.html
etc
If they are not then you will get 404s.
If your new site has the same pages as on your old site but at a different relative path then the only way to 301 redirect the old URLs is to directly cross reference them. So, for example, if the big-widgets.html page on your new site was now at a URL of widgets-big.html you would need a direct 301 redirect from oldsite.com/big-widgets.html to newsite.com/widgets-big.html for the correct page to be found.
Having rambled on about this it may be that you have done nothing like I have said (sorry about that!), but it's just that when you said "so we switched to a 301 redirect", i.e. that sounds like just one 301 redirect, not many of them.
I hope my ramblings help!
Peter