Ram, Сеть всегда доступна в режиме отладки при программировании для WP7 (эмулятор и подключенное устройство WP7), что, вероятно, является причиной того, что NetworkAvailabilityChanged никогда не срабатывает.
Я бы попробовал приложение на устройстве снова без отладки, чтобы лучше понять, что происходит.