BBC4 should be there though (I have same model) and I believe that you will find it in the same transmission block as other BBC channels. Incidentally, one trick they don't tell you about is that IF you are recording 2 channels, it is actually possible to watch a third channel IF it is on the same transmission block as one of the the others. You'll see what I mean if you try it, because most channels will appear as restricted by recording, but if you look at the available channel list, it will show more than the two you are recording.
Anyway, as Chris says, a signal booster and a rescan will generally solve most problems. It's quite safe to do this as you would an initial (as from new when bought) scan.