Okay, sounds like the index/cache is out of date. Try running "tracker-processes -r" to clear the index (this will mean it'll have to reindex all media on the phone again, so could take a while), then launch Photos/Media Player to kick the indexer back into action.