I'd suggest first checking to see if your "darkroom" is actually dark. Do what you usually do when you begin printing, but just sit there in the dark for 5 minutes until your eyes adjust, then assess how dark it actually is. It would have to be pretty bright, though, to grossly overexpose your paper.
Next check your safelight. Take a piece of paper out under safelight, put a coin on the paper, and leave it be for 5 minutes or so. Then develop the paper to see if the area exposed to safelight turns dark but the area beneath where the coin was is unaffected.
Make another test strip with your enlarger lens set at its minimum aperture. Make f/stop increments like Thomas suggested, but I'd start at 2 seconds, then 3 seconds, then 5 seconds, then 11 seconds, 16 seconds, 22 seconds, and 32 seconds. Those are roughly 1/2 stop increments.
These things might help you figure out your problem.