Installed games showing as not installed
Solution 1:
It looks like this was a bug related to Ubuntu's kernel 3.13.0-59, and was found documented and discussed on Steam's Github repo. The bug prevented Steam from accessing it's own library folders.
Ubuntu has since updated the kernel again to 3.13.0-61 and this update will resolve the issue.