Today I've tried my new lens, but the image was very distorted in the right side. Here's the image:
Is this normal? (The building on the right is very skewed)
Bigger image: link
Distortion caused by a lens's optics would give you barrel distortion (objects appear to bulge outward) or pincushion distortion (squishing inward). The skewed lines you are observing are straight; this is perspective distortion, and is not a problem caused by the lens nor fixable with better optics (you can fix it with a tilt-shift lens, but that's a special type of lens).
You can read more about exactly what perspective distortion is and how to deal with it here.
You're getting what is called Perspective distortion which is most noticable in wide angle lenses. Check out this link for more info:
Basically close up objects in the center of the frame will look enlarged while objects on the sides will be stretched away from the center of the photo.