We compute the effective permeability of a model fractured porous medium in which rectangular fractures with finite thickness are distributed in the matrix with random orientations. The local permeability of the porous matrix is spatially distributed according to a fractional Brownian motion, which induces long-range correlations in the permeabilities. Using numerical solution of the Stokes' equation, the effective macroscopic permeability is calculated as a function of a variety of factors, including the Hurst exponent that characterizes the type of the correlations, and the number density and width of the fractures. The results indicate that the correlations give rise to non-trivial effects on the effective permeability and that the assumption of a uniform matrix in a fractured porous medium leads to overall permeabilities that differ significantly from those in which the matrix is heterogeneous.