У меня была точно такая же проблема, и я решил ее, создав подкласс UINavigationController.
Затем в методе viewDidLoad я просто создаю свой фон (ImageView) и добавляю его в представление.
Если ваш UINavigationController создан из пера, просто дайте ему свое имя класса в IB. Я должен был сделать это, так как у меня также есть пользовательская панель навигации, которую вы можете установить только в IB.