Perhaps something is blocking the connection to the map server. Are you using any antivirus software or firewall like little snitch, kaperski? Then try to disable them temporarily. Check, if the maps app or Preview can show the photos on a map.
I have looked at recent photos from Lisbon, Quebec City, Cheltenham, Abu Dhabi - none of these display on maps but appear scattered on a grid as if their location is significant but the street/road map is not available.
Are you looking hit the maps in the Moments/Collections, or at the map in the Info panel, if you select a photo? I tested with photos from Quebec City and Lisbon, and both are showing on the larger map and in the Info panel. My screenshot above is from the Info panel.
Should I try altering the coordinates manually to see if that changes anything? If so, how do I do this?
You cannot yet enter new coordinates in Photos version 1.0.1, that feature is not yet supported. It will be available with the next Photos version to be released with MacOS X 10.11 El Capitan in fall. The Beta version of Photos in the current Beta release already supports it.
If you want to change the GPS tags of a photo, export it and change them in an external application - jetPhoto Studio, Geotagalog, HoudahGeo, the free exiftool. Or simply launch iPhoto again and import the photo to iPhoto. To use iPhoto with your current system, update to version 9.6.1.
Get iPhoto 9.6.1 if you didn't update before OS... | Apple Support Communities
If you are comfortable with the Terminal use the free exiftool:
See: http://www.sno.phy.queensu.ca/~phil/exiftool/exiftool_pod.html#geotagging_exampl es
To install exiftool: http://www.sno.phy.queensu.ca/%7Ephil/exiftool/install.html