what patch you used?
And are you sure that you don't try to patch it earlier patch than you current game version?
My game was patched to newer version beforehand, so I only need the patches after that. But you can try the patch 1.05 from
www.nma-fallout.com there should be any problem with that patch.
Your problem sounds quite strange. Is your cd scratched or dirty? that may affect a bit.
OH, and be sure to use correct version of patch. There is different patches to US and Europe versions. You should check that too. I think that's the problem. You have ie European version, and tried to patch it with US patch, and then the game tried to search US version of the cd, but didn't find it, only European version, and that's why it gives you that kind of error.