After adjusting my V-brake blocks to their highest setting on the lever, they still do not align with the wheel rim (they sit half on, half off).
Is there any thing I can do about this, or is it an incompatibility between the wheel size and fork?
You may have 27in wheels if you have an older bike, which are larger than typical 700c wheels found on most modern road bikes. The new fork may be made for 700c wheels and have lower v-brake mounts than your original fork, causing the reach issue.
You will either need to find brakes with longer slots on the brake arms or switch to a 700c wheel & tire in the front (you may be able to fit 700c wheels in both front and back, but you may have issues with brakes lining up in the back depending on the brakes you use)
You will find (usually an allen/hex key) bolt on the brake pad itself. Loosen that, align your brake pads then re-tigthen. You may also need to adjust again on the bars to get it to fit.
You will also find it easier when loose and aligning them, to pull the brakes right up to the rim and tighten the bolts.
Everything you need to know you will find here: http://sheldonbrown.com/rim-brakes.html