The condition of thermal equilibrium simplifies the theoretical treatment of fluctuations as found in the celebrated Einstein's relation between mobility and diffusivity for Brownian motion. Several recent theories relax the hypothesis of thermal equilibrium resulting in at least two main scenarios. With well separated timescales, as in aging glassy systems, equilibrium Fluctuation-Dissipation Theorem applies at each scale with its own "effective" temperature. With mixed timescales, as for example in active or granular fluids or in turbulence, temperature is no more well-defined, the dynamical nature of fluctuations fully emerges and a Generalized Fluctuation-Dissipation Theorem (GFDT) applies. Here, we study experimentally the mixed timescale regime by studying fluctuations and linear response in the Brownian motion of a rotating intruder immersed in a vibro-fluidized granular medium. Increasing the packing fraction, the system is moved from a dilute single-timescale regime toward a denser multiple-timescale stage. Einstein's relation holds in the former and is violated in the latter. The violation cannot be explained in terms of effective temperatures, while the GFDT is able to impute it to the emergence of a strong coupling between the intruder and the surrounding fluid. Direct experimental measurements confirm the development of spatial correlations in the system when the density is increased.