Special relativity is defined by invariants on the Minkowski metric ds^2 = dx^2 - dt^2 using general coordinates and setting c to unity. This is a generalization of the Euclid metric ds^2 = dx^2. (In Cartesian coordinates and in 2d, ds^2 = dx^2 + dy^2).
Just as the Euclidean metric fails on a gridded plane where one would instead use the Taxicab metric (ds = \sum _{i=1}^{n}|p_{i}-q_{i}|), and the problem persists to higher spatial dimensions, the 3+1 Minkowski metric of Special Relativity fails on a discretized spacetime, and one would have to use a metric appropriate for whichever dimension(s) is/are discrete. Assuming it's not just the timelike dimension that's discrete, the Taxicab metric is readily generalized to small patches of 3+1 spacetime, just like the Euclidean metric.
The other part of Special Relativity is important here: the fundamental actions that are invariant under translations, rotations and boosts -- Poincaré invariance -- is impossible to fully recover from a spacetime that does not admit the Minkowski metric; the best we can do with a metric on discretized spacetime is where the discrete steps are extremely small.
The firm upper limit, from experiment and astrophysical observation, on discretization approaches the Planck length. [0]
There is plenty of literature about violations of the full Poincaré symmetry under discrete spacetime (especially violations of Lorentz invariance; the Lorentz group is a subgroup of the Poincaré group). example at [1]
Essentially, the problem is that in a discrete spacetime a boosted observer could see a Lorentz-Fitzgerald contraction acting on the minimal length, further contracting it. The ways around that are either extremely shaky as there is lots of conflict with experiment (e.g. fixing a preferred rest frame) or extremely subtle (e.g., UV corrections to the smooth Lie groups of the Standard Model or replacements for them that reproduce existing IR results e.g. by replacing the metric with an operator (but see also [0] again vs [3]).
Some further detail on Sabine Hossenfelder's blog: http://backreaction.blogspot.co.uk/2016/04/dear-dr-b-why-is-...
[0] http://arxiv.org/abs/hep-ph/9812418
[1] https://arxiv.org/abs/hep-th/0112090
but for contrast
[2] http://arxiv.org/abs/1406.2610 and http://arxiv.org/abs/gr-qc/0405085 which shows that in a toy 2+1d model with a discrete spacetime, Lorentz invariance can be recovered by introducing non-local interactions; it is only suggestive with respect to our 3+1d spacetime, however.
[3] http://arxiv.org/abs/gr-qc/0205108