Why won't tires go on my Velocity A23 rims?
From some rather small experience I had with the problems you describe, I could give you these advices:


The first time you install a new (never used) tire is always the worst. Every tire gets a bit more "soft" to install after it's used a bit;
When you are inserting the "last bit" of tire bead, you have to be sure all the rest of the bead is centered in the rim, so that it may sink in the deepest part of the rim and release some bead for you to use the levers and put it in.
It's VERY important you pay attention to the position of the valve. It should never be opposite (180°) from the "last bit" of tire you are installing, otherwise the opposite side of the bead will not be deeply centered in the rim;
Levers should be thin. That means they must be of a very strong material, preferrably engineering plastic. I use Schwalbes (blue ones) and they are very good. Some other levers I have sometimes don't work, in these cases only the Schwalbes do, but there may be other good brands around.


At last, it's not impossible that your rim and your tire (at least the particular ones you have with you) are incompatible with each other. I would recommend you try to install the same tire in another rim, and another tire in the same rim, to check where the problem is, before asking for replacement of a part that is actually OK.

Hope this helps!