Does frame of reference affect what's considered perpendicular? Let's say we have two perpendicular lines in one frame of reference, will those lines always be perpendicular in other frames of reference?
I would say no but would like to get your opinion on the matter.
By argument goes like this: 
Let's imagine a tilted sheet of paper, so two corners are pointing east/west. An observer traveling in the east/west direction would see the angles change due to length contraction. So the angles would not be 90° anymore. Therefore orthogonality is not conserved in relativistic spacetime.
Am I right?
 A: You are correct. In order to have a constant speed of light, special relativity requires physics to be invariant under any coordinate transformation that preserves the inner product $t_1t_2 - x_1x_2 -y_1y_2 -z_1z_2$. There is a subset of these transformations that preserves the product $x_1x_2 +y_1y_2 +z_1z_2$, which hence also preserves angles between the 3 spatial coordinates $x,y$, and $z$. However, there are also transformations that preserve the whole four-coordinate product, but not the three-coordinate product. So spatial angles are not preserved under these transformations. These last transformations are the ones that mix spatial coordinates with the time coordinate, and are called boosts. The ones that preserve the three-product only mix spatial coordinates and are called rotations.
A: You are absolutely right and your reasoning is correct: boosts impart an anisotropic shrink to length scale factors, so in general spatial, Euclidean orthogonality is not preserved. The only right angles that are preserved is those between the direction of the boost and directions initially at right angles to these.
I'll even cite a practical application. The orthogonal mirrors in the retroreflectors of the LAGEOS satellites are deliberately offset from orthogonality (by about 1.5 seconds of arc each) so that, although they are not orthogonal in their rest frame, they are precisely orthogonal from the Earth frame as the LAGEOS satellite flies overhead at about 5 kilometers a second (the orbital speed at the LAGEOS altitude of 6000km) so that a laser sounding beam is turned precisely through $180^\circ$ by the retroreflectors. I say more about this and cite/link the LAGEOS retroreflector design document in my answer here.
