We cast the problem of reverse-engineering the connectivity matrix of genetic regulatory networks from a limited number of measurements as a regularized multivariate regression problem. The regularization term incorporates the prior knowledge of sparsity of genetic regulatory networks. Moreover, the genetic profiles within a measurement are assumed to be correlated with a full covariance structure. The proposed algorithm computes a sparse estimate of the connectivity matrix that accounts for correlated errors using regularized likelihood. We show that the joint estimation of the connectivity and covariance matrices improves the estimation of the network connectivity as compared to the assumption of uncorrelated measurements. Our algorithm has ln(ln(N)) sampling complexity. We test and validate our approach using synthetically generated networks.