I was reading through all of the threads on bed adhesion because all was going well for me and then all of a sudden the brim and first layer would not stick. I discovered my issue and thought I would share in case it can help anyone else.
The issue as it turns out was environmental, not the printer, filament, or the Cura settings. As it's hot right now, the air conditioning is going full blast and a ceiling fan is on low in the room. It looks like the AC vent got turned and the cold air was blowing down on the printer. As soon as I redirected the air and turned off the ceiling fan, all worked great again. I found that I'm able to turn it back on once the first layer is down.
For reference this was using Ultimaker PLA on an Ultimaker 3. Ambient temperature 75f. All settings as default for UM PLA.