Host-parasite coevolution is expected to drive the evolution of genetic diversity because the traits used in arms races, namely host range and parasite resistance, are hypothesized to tradeoff with traits used in resource competition. We therefore tested data for several tradeoffs among 93 isolates of bacteriophage lambda and 51 Escherichia coli genotypes that coevolved during a laboratory experiment. Surprisingly, we found multiple tradeups (positive trait correlations) but little evidence of several canonical tradeoffs. For example, some bacterial genotypes evaded a tradeoff between phage resistance and absolute fitness, instead evolving simultaneous improvements in both traits. This was surprising because our experimental design was predicted to expose resistance-fitness tradeoffs by culturing E. coli in a medium where the phage receptor, LamB, is also used for nutrient acquisition. On reflection, LamB mediates not one but many tradeoffs, allowing for more complex trait interactions than just pairwise tradeoffs. Here, we report that mathematical reasoning and laboratory data highlight how tradeups should exist whenever an evolutionary system exhibits multiple interacting tradeoffs. Does this mean that coevolution should not promote genetic diversity? No, quite the contrary. We deduce that whenever positive trait correlations are observed in multi-dimensional traits, other traits may trade off and so provide the right circumstances for diversity maintenance. Overall, this study reveals there are predictive limits when data only account for pairwise trait correlations and it argues that a wider range of circumstances than previously anticipated can promote genetic and species diversity.