We have studied damping in polycrystalline Al nanomechanical resonators by measuring the temperature dependence of their resonance frequency and quality factor over a temperature range of 0.1-4 K. Two regimes are clearly distinguished with a crossover temperature of 1 K. Below 1 K we observe a logarithmic temperature dependence of the frequency and linear dependence of damping that cannot be explained by the existing standard models. We attribute these phenomena to the effect of the two-level systems characterized by the unexpectedly long (at least two orders of magnitude longer) relaxation times and discuss possible microscopic models for such systems. We conclude that the dynamics of the two-level systems is dominated by their interaction with one-dimensional phonon modes of the resonators.