I have experienced this on every version of the software and on multiple phones. I have never seen a proper fix for it. I work for a major cellphone provider, and have recommended Spotify to many people looking for a one stop destination for music.
However, because of this issue, I am seriously considering dropping my service, and moving to a competitor. This was an issue in the software going back to when I first started service and it hasn't been fixed. That shows a disregard for the customer's experience, and that is not acceptable.
The most common reason for the red exclamation is that tracks fail to download either because of memory shortage (spotify recommend having at least 500MB free) or because you have hit the limit of 3,333 offline tracks. If neither of these apply to you, please check out the troubleshooting post.