The cloud icon is the "iCloud Download" if there is an arrow through the cloud pointing down it means the tune is in iCloud and is not stored on your computer, however assuming you have an internet connection it can still be played. If there is no cloud icon by the tune it means it is stored on your computer.
On my screen I have another option iCloud Status which is a text field that says something like "purchased". The fact your settings are not holding would seem to indicate a preference file problem, but a search of com.apple.tunes.plist did not turn up any settings I could identify as controlling those settings. Neither can I explain why the iCloud Status option is not showing on your computer.
Have you considered a call to Apple Tech Support?
