He estado un buen rato buscando, y no hay nada que baje de los 8€ y pico... (incluyendo gastos de envío)
Hay una tienda española electan.es, en el que sale algo más económico (BOB-12009 Sparkfun Conversor Lógico de Nivel 3.3V-5V Sparkfun), 6€, pero tengo que hacer un pedido mínimo de 15€... Y justamente hace 3 días les hice un pedido... 
Sobre lo que comanta Sgo, he estado buscando transistores, y este creo que podría valer: MAX3223. (Me saldría bastante más barato) Pero no tengo ni idea de como se conectaría xD
Por cierto, tengo una duda sobre lo que hace el conversor de niveles que me has señalado, SrDonGato. A ver si lo he entendido bien... lo que hace es que la señal que va del pin serie del GPS al arduino, la transforma de 3.3V a 5V, y cuando se envía alguna señal del arduino al GPS, se transforma de 5v a 3.3v. ¿Es eso, verdad?
Una última duda que tengo... he estado mirando bien las características de mi arduino (mega), y he visto esto:
Serie: 0 (RX) y 1 (TX),Serie 1: 19 (RX) y 18 (TX); Serie 2: 17 (RX) y 16 (TX); Serie 3: 15 (RX) y 14 (TX). Usado para recibir (RX) transmitir (TX) datos a través de puerto serie TTL. Los pines Serie: 0 (RX) y 1 (TX) estan conectados a los pines correspondientes del chip FTDI USB-to-TTL.
Este chip FTDI es el mismo que transforma los 5V del arduino, en 3.3V para el pin del arduino que proporciona ese voltaje.
3V3. Una fuente de voltaje a 3.3 voltios generada en el chip FTDI integrado en la placa. La corriente máxima soportada 50mA.
Significará que los pines 0 y 1, dan 3.3V en vez de los 5V normales??
Muchísimas gracias por vuestra ayuda!! 