I changed the PIC and it fixed the problem.

Here is the current code for anyone who might be interested in such interfacing.

Code:
'based on: http://list.picbasic.com/forum/messages/6851/7091.html?1080565370

@ device  pic16F684, intrc_osc_noclkout, BOD_OFF, PWRT_OFF, wdt_off, mclr_off, protect_off

'quid freq horloge requise?

DEFINE OSC 8			'set OSC value to 8MHz for instructions PAUSE, PAUSEus and SOUND (instead of default 4MHz)
DEFINE LCD_DREG PORTC 'data port out is portC
DEFINE LCD_DBIT 0 'data on portC0-portC3
DEFINE LCD_RSREG PORTC 'r/s is on portC.4, with 10K WPU
DEFINE LCD_RSBIT 4
DEFINE LCD_EREG PORTC 'enable is on portC.5
DEFINE LCD_EBIT 5
DEFINE LCD_BITS 4 '4bits data bus
DEFINE LCD_LINES 2 '2lines display
DEFINE LCD_COMMANDUS 2000 '2ms cmd delay
DEFINE LCD_DATAUS 50 '50us data delay

INTCON = 0      'disable interrupts and clear int flags
OSCCON = %01110001	'int osc, hs, 8mhz
CMCON0 =  %00000111
ANSEL = %00000000
OPTION_REG = %11111111

TRISA = %000001 			
TRISC = 0 

PORTA = %000000   'A0 is used for gps input, SERIN2 bitbanging (software eusart)
PORTC = 0

WPUA = 0 			

hh VAR BYTE 'hours
mm VAR BYTE 'minutes
ss VAR BYTE 'secondes
sss var word   'centiemes de seconde
knots VAR WORD 'speed in knots (units)
knotsten VAR BYTE 'speed in knots (tens)
kmph var WORD
course VAR WORD 'heading
latdeg VAR BYTE 'degrees latitude
latmin VAR BYTE 'minutes latitude
NS VAR BYTE 'north or south
londeg VAR BYTE 'degrees longitude
lonmin VAR BYTE 'minutes longitude
EO VAR BYTE 'east or west
j VAR BYTE 'day
m VAR BYTE 'month
a VAR BYTE 'year
fix VAR WORD 'GPS fix
'for kmph calculation
Speed Var byte[5] 
SpeedKnots VAR WORD 
SpeedKm VAR WORD 
Temp VAR BYTE 
Dummy VAR WORD
i var byte
latsec VAR word
lonsec VAR WORD
satellites var word

b1 var byte
b2 var byte

course_ CON 0
latdeg_ CON 10
latmin_ CON 20
londeg_ CON 30
lonmin_ CON 40
kmph_ CON 50
satellites_ con 60
'programming custom characters
LCDOUT  $FE,$40,$00,$0A,$0A,$00,$11,$0E,$00,$00  ' Cust Char #0: happy smiley  
LCDOUT  $FE,$48,$0E,$15,$1B,$19,$1B,$15,$0E,$00  ' Cust Char #1: copyright
LCDOUT  $FE,$50,$0E,$0E,$1F,$0E,$04,$00,$1F,$00  ' Cust Char #2: press  
LCDOUT  $FE,$58,$0A,$1F,$1F,$1F,$0E,$04,$00,$00  ' Cust Char #3: heart  
LCDOUT  $FE,$60,$03,$05,$19,$19,$19,$19,$05,$03  ' Cust Char #4: speaker  
LCDOUT  $FE,$68,$00,$00,$04,$0E,$0E,$0E,$0E,$00  ' Cust Char #5: bullet  
LCDOUT  $FE,$70,$1F,$11,$11,$11,$11,$11,$11,$1F  ' Cust Char #6: empty square  
LCDOUT  $FE,$78,$04,$0E,$1F,$0E,$0E,$00,$1F,$00  ' Cust Char #7: release

LCDOUT $fe,1,"GPS device"
LCDOUT $fe,$c0,"25.11.09"
PAUSE 2000

gps:
'LCDOUT $fe,1,"Serin start1"
'PAUSE 1000
SerIn2 PORTA.0,188,3000,toto,[wait("$GPRMC"),wait(","),DEC2 hh,DEC2 mm,wait(","),fix,wait(","),DEC2 latdeg,DEC2 latmin,wait(","),NS,wait(","),DEC3 londeg,DEC2 lonmin,wait(","),EO,wait(","),knots,wait("."),DEC2 knotsten,wait(","),DEC3 course,wait(","),DEC2 j,DEC2 m,DEC2 a]   'works
If fix !="V" THEN
    LCDOUT $fe,1,"Fix: ",#fix
    LCDOUT $fe,$c0,"65:bad; 86:good"
    PAUSE 1000
ENDIF
'LCDOUT $fe,1,"FOUND"
'PAUSE 1000
'IF (fix != "V") Then 
'	LCDOut $FE, 1 'Clear Screen 
'	LCDOut "No Fix"
'    LCDOUT $fe,$c0,"Fix: ",#fix 
'	Pause 1000
'    GOTO gps
'ENDIF
GOSUB display1
'LCDOUT $fe,1,"Serin start2"
'PAUSE 1000
'$GPVTG,360.0,T,348.7,M,000.0,N,000.0,K*43
SerIn2 PORTA.0,188,3000,toto,[wait("$GPVTG"),wait("N"),DEC3 kmph]
'LCDOUT $fe,1,"FOUND"
'PAUSE 1000
GOSUB display2
'LCDOUT $fe,1,"Serin start3"
'PAUSE 1000
'$GPGSV,2,1,07,07,79,048,42,02,51,062,43,26,36,256,42,27,27,138,42*71
SerIn2 PORTA.0,188,3000,toto,[wait("$GPGSV,"),SKIP 1, wait(","),SKIP 1, wait(","),DEC2 satellites]
'LCDOUT $fe,1,"FOUND"
'PAUSE 1000
GOSUB display3
GOTO gps

toto:
LCDOUT $fe,1,"timeout"
PAUSE 1000 
GOTO gps


display1:
WRITE course_,course
LCDOut $FE, 1 'Clear Screen 
LCDOut "HEADING:",DEC3 course," DEG"
Pause 3000
write latdeg_,latdeg
write latmin_,latmin
WRITE londeg_,londeg
WRITE lonmin_,lonmin
LCDOut $FE, 1 'Clear Screen 
LCDOut "LAT:",DEC2 latdeg,",",DEC2 latmin," ",NS
LCDOut $fe,$c0
LCDOut "LON:",DEC2 londeg,",",DEC2 lonmin," ",EO
Pause 3000
RETURN

display2:
WRITE kmph_,kmph
LCDOUT $fe,1,DEC3 kmph," km/h:"
PAUSE 3000
if kmph > 50 then
    HIGH porta.1
ELSE
    LOW porta.1
ENDIF
RETURN

display3:
write satellites_,satellites
LCDOUT $fe,1,DEC3 satellites," satellites"
PAUSE 3000
RETURN