Todos los síntomas que das, están relacionados; es decir, no te arrancaba bien a la primera por tener baja la carga de la batería. Al poner una batería nueva, aunque la tensión sea la correcta (voltios), no tiene por que tener toda la carga (amperios). Es recomendable realizar un trayecto de carretera, sin pausa, de 100km +/-. Lo que te hacían los calentadores (parpadeo), también está relacionado con la carga de la batería, date cuenta que un calentador es una pequeña resistencia eléctrica, casi un cortocircuito (0.5 a 1.5 ohmios normalmetne). Si tenías la carga baja, pues eso, que hace cosas raras. El funcionamiento normal de los calentadores es que en la puesta en servicio (posición antes de arrancar) esté el piloto activo una cantidad de tiempo determinada por la centralita (módulo de la inyección) en función de la temperatura.
En cuanto al aire en la alimentación de combustible, no hay problema ya que las bombas de inyección desde el año 2000/2002 aproximadamente son autopurgantes. Si después del cambio ha arrancado, no tendrás aire en el cirucito de alimentación.
De todos modos, haz caso del resto de respuestas y comprueba que los bornes de la batería, además de estar limpios, estén bien apretados. Es recomendable aplicar una película muy fina de baselina almenos en el borne positivo.
Espero que te sirva esta respuesta. Ya nos contarás.