Not sure if this post is still active. I typed in "mathematics Proofs" into amazon books and got 5-7 decent looking books. Rotman is a good author I think …
I sympathize with your situation. I think a book like Velleman's could potentially be helpful.
Ultimately it is just a hard road learning about proofs. But it is fun as you get the hang of it. Get a tutor once in a while for feedback.
I made my transition to advanced math using Spivak's book. I took a class using it in my first year after high school, and it took lots of time to get used to and help from friends over beers. Then I had a great Summer working through Spivak a second time slowly doing all the problem sets form the more advanced class. It was a formative experience for me. (I eventually got my Ph D and was in academics for a while, but will probably move on soon.)
So advice on Spivak: Yes, give it time … keep working at problems, go over it again and again.
Get some help, talk to people if you know any. Learning math is very osmotic I think. It is very helpful to have someone who has it in their bones give you a feel for it.
For limits, I found it helpful to just focus on polynomials at first. Spivak does a detailed example. You can follow the same pattern for any polynomial, like an algorithm for how to write the proof. Once I had that under my belt, I gained some confidence with limit proofs.
For properties of real numbers it is a bit subtle and you will gain more and more appreciation of their subtle aspects as you go on. Don't get hung up on it.
I looked at Velleman's book you mentioned. Seems like it should help a bit. But don't get stuck there, jump into proofs and problems that really interest you, there are lots of cool ones in Spivak.
If Velleman doesn't help try some of the ones you get after typing "mathematics proofs" into amazon.
Here are some. Unfortunately I cannot recommend any one in particular (I believe Rotman is a good author). Good luck.
Mathematical Proofs: A Transition to Advanced Mathematics (3rd Edition) (Featured Titles for Transition to Advanced... by Gary Chartrand, Albert D. Polimeni and Ping Zhang (Sep 27, 2012)
Proof in Mathematics: An Introduction by Albert Daoud and James Franklin (May 17, 2012)
Proofs and Fundamentals: A First Course in Abstract Mathematics by Ethan D. Bloch (Jun 1, 2000)
Journey into Mathematics: An Introduction to Proofs (Dover Books on Mathematics) by Joseph J. Rotman (Dec 21, 2012)
A Transition to Mathematics with Proofs (International Series in Mathematics) Hardcover – December 30, 2011
by Michael J Cullinane