We present a Galilean invariant, momentum conserving first order Brownian dynamics scheme for coarse-grained simulations of highly frictional soft matter systems. Friction forces are taken to be with respect to moving background material. The motion of the background material is described by locally averaged velocities in the neighborhood of the dissolved coarse coordinates. The velocity variables are updated by a momentum conserving scheme. The properties of the stochastic updates are derived through the Chapman-Kolmogorov and Fokker-Planck equations for the evolution of the probability distribution of coarse-grained position and velocity variables, by requiring the equilibrium distribution to be a stationary solution. We test our new scheme on concentrated star polymer solutions and find that the transverse current and velocity time auto-correlation functions behave as expected from hydrodynamics. In particular, the velocity auto-correlation functions display a long time tail in complete agreement with hydrodynamics.