Actually the problem is the opposite of what you stated. A +1 bonus with 4DF when you are dealing with opposed rolls has a far greater impact than a +1 with 3d6 and 1d20.
To see this, take a look at this anydice At Least graph. You will see that the first set of result has a result of 0 occurring at least 61.73 percent of the time. And +1 occurs at least 38.27 percent.
At +1 to the die roll then +1 occurs at least 61.73 percent of the time as you can see in the second set of results. This is an improvement of 23 percent!
I first noticed this when I was playing a Fudge based RPG that I wrote. It doesn't show up right away but as more session were run it was obvious that a +1 bonus was a big deal in a way it isn't with other systems.
I wrote a combat simulator to check this and sure enough when I give one of the fighter a +1 skill the odds shifted dramatically over 10,000 fighters. The reason it doesn't show up right away because as you noted the result of a fudge die is from -4 to +4. Which can and does swamp a +1 or even a +2 difference in ability on an opposed roll.
Plus we are talking about tabletop roleplaying where the character can find themselves in a variety of circumstances that make the fights more than just two guys wacking away at each other like in my simulation.
To sum this up, what you are seeing is just bad luck on your group's part. Over time the frustration that build when dealing with opponents that are more skilled in opposed situation will be a far bigger issue than the range of result from the Fudge Dice.
As a final note, note the shape of the bell curve of 4dF on anydice versus that of a 3d6. Fudge dice have a more dramatic peak in the middle. This is what causes the issues that I been seeing.
Best Answer
In Fudge, your character has skills and abilities that are ranked on the Fudge Scale: Terrible -3, Poor -2, Mediocre -1, Fair 0, Good +1, Great +2, and Superb +3. The dice, 4dF are zero-centered. You typically roll the dice and add the result to your relevant skill to determine the outcome of your attempt. An elegant system in all actuality.