It doesn't take a particular apple variety to pollinate another apple tree, just a different variety blooming at the same time. If your current apple tree produced just fine, there are other apples close enough to pollinate it so maybe there's one to pollinate the Fuji too. Even a crabapple will work.
