We present the results of a Herschel survey of 21 late-type stars that host planets discovered by the radial velocity technique. The aims were to discover new disks in these systems and to search for any correlation between planet presence and disk properties. In addition to the known disk around GJ 581, we report the discovery of two new disks, in the GJ 433 and GJ 649 systems. Our sample therefore yields a disk detection rate of 14%, higher than the detection rate of 1.2% among our control sample of DEBRIS M-type stars with 98% confidence. Further analysis however shows that the disk sensitivity in the control sample is about a factor of two lower in fractional luminosity than for our survey, lowering the significance of any correlation between planet presence and disk brightness below 98%. In terms of their specific architectures, the disk around GJ 433 lies at a radius somewhere between 1 and 30au. The disk around GJ 649 lies somewhere between 6 and 30au, but is marginally resolved and appears more consistent with an edge-on inclination. In both cases the disks probably lie well beyond where the known planets reside (0.06-1.1au), but the lack of radial velocity sensitivity at larger separations allows for unseen Saturn-mass planets to orbit out to $sim$5au, and more massive planets beyond 5au. The layout of these M-type systems appears similar to Sun-like star + disk systems with low-mass planets.