Sounds like two problems, the radiator needs recored and the fan size being too small.
Since you have a 6400 series, your radiator should be a 4 row, and should be taller than one from a pickup. It will probably require a custom made core, which is why the price is so high. You might try calling a shop in a bigger city, but you will need to have the dimensions of the core in order to get a price. See what you find. I think the local shop is kind of high, but you never know.
