The property holds for all $n$ but $5.$ Consider first a regular $2n$-gon for $n \ge 2.$ Let $A_i$ and $A_j$ be $2$ vertices which are diametrically opposite. If $A_{\sigma (i)}$ and $A_{\sigma (j)}$ are still diametrically opposite, then any third vertex $A_k$ will work since $\angle{A_{i}A_{k}A_{j}} = {90}^{\circ} = A_{\sigma (i)}A_{\sigma (k)}A_{\sigma (j)}.$ Otherwise, let $A_k$ be the vertex such that $A_{\sigma (k)}$ is diametrically opposite to $A_{\sigma (i)}.$ Then $\angle{A_{i}A_{k}A_{j}} = {90}^{\circ} = A_{\sigma (i)}A_{\sigma (j)}A_{\sigma (k)}.$ Note that this is trivially true for an equilateral triangle, but it's false for a regular pentagon (consider $ABCDE$ and $A'D'B'E'C'$). Consider now a regular $2n+1$-gon for $n \ge 3.$ Clearly there are no right triangles. The number of obtuse triangles with a particular diagonal as the longest side is equal to the number of vertices between the endpoints of this diagonal, going the shorter way. Since there are $2n+1$ diagonals of each length, the total number of obtuse triangles is \[(2n+1)\sum_{i=1}^{n-1}{i} = {1\over2}(n-1)n(2n+1).\] The total number of triangles is \[\dbinom{2n+1}{3} = {1\over3}(2n-1)n(2n+1).\] Since \[ { {{1\over2}(n-1)} \over{{1\over3}(2n-1)}} = {1\over2} + {{n-2}\over{4n-2}} > {1\over2}\] for $n \ge 3,$ there are more obtuse triangles than acute ones. By pigeonhole, there exist $3$ vertices such that their initial and permuted positions both determine obtuse triangles.