I hadn't really looked at Catullus in a while; pulling him off my shelf for a quick glance over I see that he's not as difficult as I remember. I think maybe I'm influenced by the fact that when I started reading Latin, I began with Caesar (who everyone says is the easiest, but whom I struggled with at the time), and then moved to the Aeneid, which I found much easier to follow. Looking back, I think the thing that got me with Caesar is that he uses some very un-English constructions - the different uses of 'quod' drove me crazy, and I got lost in his complex series of infinitives - while Vergil is more of a straightforward storyteller. But now that I look back at Catullus, his constructions are generally shorter and more simple than Vergil's, and his vocabulary seems smaller. Actually, I am enjoying reading Catullus right now, because his poems are short enough that I can read through each fairly quickly. I still don't think Vergil or Ovid are that difficult, but I will concede that Catullus might be easier (although http://www.faqs.org/faqs/classics-faq/
rates Catullus and Vergil as 6/10 in difficulty, and Ovid as 5/10). Also, keep in mind that commentaries and help are probably more readily available for Vergil that Catullus.