In multi-physics computations where a compressible fluid is coupled with a linearly elastic solid, it is standard to enforce continuity of the normal velocities and of the normal stresses at the interface between the fluid and the solid. In a numerical scheme, there are many ways that velocity- and stress-continuity can be enforced in the discrete approximation. This paper performs a normal mode stability analysis of the linearized problem to investigate the stability of different numerical interface conditions for a model problem approximated by upwind type finite difference schemes. The analysis shows that depending on the ratio of densities between the solid and the fluid, some numerical interface conditions are stable up to the maximal CFL-limit, while other numerical interface conditions suffer from a severe reduction of the stable CFL-limit. The paper also presents a new interface condition, obtained as a simplified characteristic boundary condition, that is proved to not suffer from any reduction of the stable CFL-limit. Numerical experiments in one space dimension show that the new interface condition is stable also for computations with the non-linear Euler equations of compressible fluid flow coupled with a linearly elastic solid.