In most cases, if you get Fix VirtualBox: Fatal: Could not read from Boot Medium! System Halted Error, it means you need to mount a bootable CD ISO image or need to put a bootable CD like the Ubuntu or Windows install disk in the CD tray.
In some cases, it can also mean you forgot to mount your virtual system hard drive or your Operating System is corrupt and is not bootable.
Read my post on Mount a CD image ISO file or Virtual Hard drive in Virtual Box Virtualization software Video and Adding + Removing Virtual Hard Drive CD-Rom to Virtual box video to learn how to mount, or add a bootable virtual drive to VirtualBox and fix this error.
In more serious cases, this error can also mean your operating system or bootable partition is corrupt, and you need to boot your recovery disk or operating install disk or ISO to fix this problem. This is one of the many reasons why you should backup your virtual hard drives to another drive like a 1 TB USB 2.0 External Hard Drive.