Try to coat and develop one paper in complete darkness without any safelight. This way you can rule out safelight fog.

Which kind of safelight do you use and are you sure there is no light leaks when you coat and process?