Brakes are made in different "reaches". There are "standard" reach brakes the worked well with most applications, but there are also "short" reach, generally for compact race bikes and long reach for other applications, such as mounting 700c wheels on a frame designed for 27" wheels. Further there is no standard for short or medium reach, so a medium brake for one brand may be a short on another; Campagnolo brakes run short. Some frames may be designed for medium reach brakes, but the medium brakes you are using are s shorter medium (again this is typical of Campy). As Bianchll said older cheaper frames and/or forks were made for a 27" standard that is larger than the 700c standard. If you have a frame made for a 700c wheel and a fork made for a 27" wheel, then the front brake would need a longer reach to work with a 700c wheel. Further just because a frame or fork was designed for medium brakes, does not mean the front and rear brakes reach will be identical. The front is usually on the short end of the pad adjustment and the rear on the long end. However, a 1/2 is a lot of difference, so it's likely your fork does not match your frame. Long reach brakes are still available however;
http://www.rivbike.com/Sidepulls-Centerpulls-s/116.htm or
http://sheldonbrown.com/harris/brake-calipers.html are some good choices.