I think Matt meant that this is what you normally should see when a file is not available:
It works for me. Since you mentioned that also you see the "red x" icons you should get the same message.
Does the problem exist with all file or media formats or only with a specific format? A playback log might provide more information (you can access the logging options in Help > Logging).
If you use Library Server and the server itself has lost the connection to a media file that is located on a separate file server, I think the client may not be able to provide similar information about the file status and may behave differently. However, the "red x" icons should not show up when the Library Server / Client feature is used so probably your problem is different.