Telefonie nicht möglich! Netzbetreiber schuld?

Never ending story:

Seit Februar schlag ich mich nun mit meinem Android-Problem rum! (siehe andre Threads)...
Stand der Dinge:
Ich habe zwei Android Phones (Motorola Milestone und Htc Legend), keines von beiden funktioniert mit meiner Sim-Karte (Vertrag) von Base. (bei dem ersten dachte ich noch es sei defekt... aber nun hab ich ja ein weiteres neues Handy)
Telefonie in Festnetz möglich, auf Mobilfunknummern allerdings nicht und Sms schreiben nur manchmal über die Schnellnachrichtfunktion im Popup-Fenster.

Sobald ich eine Handynummer wähle kommt die Ansage: "Die von Ihnen gewählt Rufnummer ist aus dem eplus-Netz nicht erreichbar"
Auf Nachfrage bei Base, habe ich eine neue Sim-Karte bestellt (vielleicht ist ja die alte verschlissen).

Diese ist dann gestern direkt aktiviert worden. Kein Unterschied, telefonieren trotz vollem Empfang funktioniert weiterhin nicht! Erreichbar bin ich allerdings... Internet via Netzbetrieber funktioniert einwandfrei!

Habe D1, o2, Base und Eplus Sim Karte in beiden Telefonen ausprobiert, funktionierten auch problemlos. Nur eben nicht meine! Kein Sim-Lock, kein Branding...
Base scheint ratlos bis jetzt...

1. Kennt jemand die Ursache für solche Probleme?
2. Schonmal von so einem Fall gehört?
3. Was kann ich tun, wenn Base sagt es läge an den beiden Handys oder dem Android-Betriebssystem?

Brauche dringend Hilfe!

1. Habe ich grade gefunen das gab es wohl schonmal. Nicht bei mir aber im Netz ;-)
Seine Lösung: Base Technik Hotline anrufen -> Telefonnetz rebooten lassen das Datennetz funzt ja
2. Eigentlich nicht jetzt das erste mal
3. Daran kanns nicht liegen ... bei anderen funzt es ja auch

"Die von Ihnen gewählt Rufnummer ist aus dem eplus-Netz nicht erreichbar" diese ansage kommt nur bei gesetzen Rufnummernsperren, macht Base , Eplus sehr gerne bei teuren Nummern oder Callback-Services, ist auf jeden Fall ne Eplus Sperre

Das haben die mir auch schon erklärt, dass diese Ansage eigentlich garnicht kommen dürfte... Sie wissen von keiner Sperre!
Wieso auch sollten normale Handynummer gesperrt sein? Und warum nur von den beiden neuen Telefonen aus und nicht meinem alten SE?
Können die einen Reboot separat nur für meine Netzeinstellungen durchführen?