Leicht OT: Vorwahl für Auslandsgespräche

Ich habe eine Fritzbox 7490 an einem 100/40 VDSL Anschluß der Telekom. Daran sind zwei FritzFon Mobilteile.
Als ich damit letztens mal nach Spanien telefoniert habe, funktionierte das nur mit der Vorwahl 000034 . Normalerweise würde man ja 0034 oder +34 erwarten, aber beides lieferte eine unbekannte Nummer.
Hat jemand eine Ahnung warum ich da vier Nullen wählen muss bzw. Was man ändern muss, damit das mit zwei Nullen geht?
Nationale Ferngespräche funktionieren übrigens ganz normal.