Step Zero: is always to check/adjust the bed level - if the height over the bed varies while putting down the first layer, it's hard to ever get first layer settings that work.
Step One: is to adjust your first layer settings - height, temperature, extrusion width until you find a set that work for your setup (knowing that they may change somewhat when you change filament.) Some folks find more success with thin first layers, others with a thicker first layer to pump more plastic, still others use the same layer height but increase the width to pump more plastic, and others combine these approaches. Increasing the temperature is common, though in my case I found that the "usual" +5°C was not enough for the present setup.
You can change one setting at a time and have an idea of what works better or worse in each case, or you can change lots of settings and hope you get lucky. I prefer the tedious approach, it's less maddening.
Are you using any surface treatment on the bed? A bit of gluestick or hairspray may help you stick.