Ublox NEO-6M not getting fix on Arduino power, works otherwise - Power issue?

Hi to all,

Newbie here. Hopefully this is correct category for my question. I have problems with GPS Neo 6M getting a fix. I bought this module with USB interface: http://www.ebay.com/itm/381839915514.

If I connect it via USB directly on smartphone charger it gets a fix
If I connect it on PC (via USB) it gets a fix and shows correctly in u-center
If I connect it via USB in my car with cigarette charger it gets a fix
If I connect it to my Arduino via USB interface or directly on pins it does not get a fix
If I connect it to my laptop via USB it again does not get a fix

In any case ublox is powered with 5V regulated power. Arduino itself is powered with small car battery (12V). I thought this is a ground plane issue, but I tried all different configurations without success. There is enough current available (ublox is using cca. 70 mA).

Can anyone help me figuring out this weird behaviour? I am banging my head against the wall for the last 2 weeks about it. Let me know if I missed some important info.

Thanks!