Interfacing atomically thin van der Waals semiconductors with magnetic substrates enables additional control on their intrinsic valley degree of freedom and provides a promising platform for the development of novel valleytronic devices for information processing and storage. Here we study circularly polarized photoluminescence in heterostructures of monolayer MoSe$_2$ and thin films of ferrimagnetic bismuth iron garnet. We observe strong emission from charged excitons with negative valley polarization, which switches sign with increasing temperature, and demonstrate contrasting response to left and right circularly polarized excitation, associated with finite out-of-plane magnetization in the substrate. We propose a theoretical model accounting for magnetization-induced imbalance of charge carriers in the two valleys of MoSe$_2$, as well as for valley-switching scattering from B to A excitons and fast formation of trions with extended valley relaxation times, which shows excellent agreement with the experimental data. Our results provide new insights into valley physics in 2D semiconductors interfaced with magnetic substrates.