根据题意,红色至少要涂两个圆,而且相邻两个圆所图颜色不能相同,则红色只能涂第一、三个圆、第二、四个圆或第一、四个圆,
分3种情况讨论:
①、用红色涂第一、三个圆,
此时第2个圆不能为红色,有4种涂色方法,第4个圆也不能为红色,有4种涂色方法,
则此时共有4×4=16种涂色方案;
②、同理,当用红色涂第二、四个圆也有16种涂色方案;
③、用红色涂第一、四个圆,
此时需要在剩下的4种颜色中,任取2种,涂在第二、三个圆中,有A42=12种涂色方案;
则一共有16+16+12=44种不同的涂色方案;
故选:C.