It sounds like a combination of too wide a tyre, too narrow brake bosses on the frame & the brakes themselves. Best scenario I can think of is a narrower tyre or fit some brakes such as Shimano LX V-brakes with the parallelogram linkage, the arms sit much wider apart, outboard of the linkage.