In this paper, we analyze the impact of compressed sensing with complex random matrices on Fisher information and the Cramér-Rao Bound (CRB) for estimating unknown parameters in the mean value function of a complex multivariate normal distribution. We consider the class of random compression matrices whose distribution is right-orthogonally invariant. The compression matrix whose elements are i.i.d. standard normal random variables is one such matrix. We show that for all such compression matrices, the Fisher information matrix has a complex matrix beta distribution. We also derive the distribution of CRB. These distributions can be used to quantify the loss in CRB as a function of the Fisher information of the non-compressed data. In our numerical examples, we consider a direction of arrival estimation problem and discuss the use of these distributions as guidelines for choosing compression ratios based on the resulting loss in CRB.