Hi, been playing all day with a new gps device, i had the same problem at first but was easily sorted. for me i had to ensure the correct pin was selected as the GPSRX.
SoftwareSerial nss(3, 4);
in the above line 3 is the rx pin and 4 is the tx pin
also ensure the correct BAUD rate is selected
nss.begin(4800);
i had to change mine to 38400 but yours may be different.
hope this helps