I have some fairly extensive experience with Rudin, and I had some similar issues to you.
When I was in high school I visited a book store and purchased Rudin saying "I'm good at calculus, this must be the next step!" Of course, I was sadly mistaken. I managed to muddle through a fair amount of the book doing about half the exercises (how much I actually understood is up for debate). It was really rough. Looking back though I am able now to identify the things that made the book very difficult for me.
First and foremost though, and this goes with almost ALL beginning upper level mathematics, was that I was not really well acquainted with the difference between a "function" and a "map". In other words, I was not used to thinking about a function as being defined on anything other than it's maximal domain and it's codomain being just it's image. So, notions of countability and the lot got me all kinds of confused. In the same vein, I was unable to follow a lot of proofs (the one that sticks in my head is that the image of compact under continuous is compact) because the idea of manipulating preimages via unions and the sort was foreign to me. If you want to be successful at Rudin I suggest you get very comfortable with the basics of set theory, as laid out in the beginning of a book like Munkres.