Page returns 404 for specific permalink

Check your database, in the postmeta table, for meta_key _wp_old_slug. When you change a slug, WP stores it and automatically redirects the old to the new, which sounds like the reason you initially couldn’t access /locations/.

Once you delete the postmeta, visit Settings > Permalinks for good measure (this refreshes permalinks) and try either using an incognito window or a HTTP header checker to verify whether the /locations/ URL is working as intended. Your browser caches redirects, so just checking in a regular window is likely to be misleading.