Instead of connecting the external supply to Vin can you try connecting to the barrel connector ? It shouldn't make any difference but you never know.
The problem only happens when you use the relay. You have still not provided a link to it or details of its current consumption.