To get one thing out of the way first: toxic does not always mean the same thing. Some things are acutely toxic (e.g. carbon monoxide), some things are toxic upon accumulation (e.g. lead). Some things can get removed from the organism given enough time (e.g. methanol), some things will stay in your body ‘forever’ (e.g. lead). Some things kill you quickly (e.g. cyanide) while others will cause cancer that will kill you in maybe decades (e.g. benzene). And the organism can cope with some things given small enough concentrations (e.g. nitrite) while others are harmful at even the smallest concentrations (e.g. dimethyl mercury). Paracelsus is typically quoted in German with the saying:
Alle Dinge sind Gift, und nichts ist ohne Gift; allein die dosis machts, daß ein Ding kein Gift sei.
(All things are poison and nothing is without poison; only the dosis determines that a thing may not be poison.)
Thus, the question is only which category oxygen falls into: both in terms of acute/chronic/instant/accumulative/… and in terms of $\mathrm{LD_{50}}$ values.
Oxygen is, in principle, a very reactive gas. It is very electronegative and often reacts from its neutral $\pm 0$ oxidation state to compounds in which it features a $\mathrm{-II}$ oxidation state.
Life and living matter builds on being able to selectively use this type of oxidation enthalpy for its own uses, i.e. to build up complex structures (proteins, DNA) or to overcome entropic problems. From its beginning, ‘life’ was basically a method of using inspecific chemical energy for its own uses. Spontaneous reactions out of life’s control are typically suppressed as well as possible, workarounds made and so on. For example, aldehydes are useful, reactive chemical species that can be derivatised in may different reactions. Living organisms tend to make use of similar chemistry (as least partially) but it also tends to avoid the generation of free aldehydes as much as possible. Indeed, one way life keeps aldehydes ‘safe’ is by masking them as Schiff bases or as acetals (e.g. sugars). Life relies a lot on in situ generation of reactive species.
Indeed, imagining an evolution of the first living being in an oxygen-rich surrounding is very hard. When the first life forms came into being, the atmosphere and the conditions on Earth were generally much more reductive, much less oxidative than today. The first living organisms probably used chemosynthetic energy sources that did not rely on oxygen. It took a while for organisms to develop photosynthesis. This had quite a number of beneficial effects for those organisms: the light energy source is much more easily accessible, carbon dioxide to build up organic molecules was plentiful and these organic molecules could then be synthesised according to the organism’s needs either as building blocks or as an energy source. Photosynthesis only has one disadvantage: It has a strongly toxic by-product which can ruin the carefully-tuned enzymes your cell has by oxidising their metal cores, their sulfur atoms and more; and it can react with other molecules in the cell in unwanted ways. It had to be removed from the cell and the first photosynthetic life forms indeed proceeded to dump it into the environment.
At first, the dumped oxygen would react with reactive species and be chemically bound e.g. in rocks at the ocean floor. Partially, it was also absorbed and diluted in the oceans. After a certain oceanic concentration was reached, oxygen was released into the atmosphere and started to accumulate in land-side oxygen sinks by similar mechanisms. After all these oxygen sinks (‘dumps’) were filled, atmospheric oxygen levels began to increase dramatically within a few million years.
The effect that this had on existing life forms — even during the early evolution of oxygen-generating organisms — was catastrophic (hence the term Oxygen Catastrophy). Most life forms — obligate anaerobic ones — would have become extinct and paved the way for an entirely new generation of species: oxygen-tolerant and finally aerobic ones. The obligate anaerobes had no method to control cellular oxygen while later forms had these mechanisms in place.
The great advantage of having molecular, atmospheric or ocean-dissolved oxygen as an energy source is that it can supply a lot more energy than non-oxygenic processes: think of the amount of heat generated by burning and compare that to most other chemical processes to understand the difference. However, any organism relying on the use of oxygen must also cope with the by-products that can occur during oxidation — both desired oxidation procedures and undesired, spontaneous ones. Aerobic organisms tend to have a large battery of peroxidases and superoxide-dismutases for the controlled degradation of peroxides $\ce{R-O-O-H}$ and superoxides $\ce{H-O-O^.}$ — even though these species autodegrade almost at diffusion-controlled rates. The reason is that these reactive species, generated by the use of oxygen, would create too much havoc to allow them to degrade themselves; organisms must degrade them specifically and with minimal danger to the cell as quickly as possible.
And this is also the question why high oxygen levels can be considered toxic. Oxygen reacts with organic molecules present in the cell in an undesired fashion to generate the more reactive peroxides and superoxides. If they cannot be captured and destroyed quickly enough, they create more havoc by randomly oxidising further parts of the cell in undesired fashions potentially causing protein malfunction, DNA damage, cell wall damage and more. The higher the exterior oxygen concentration, the higher the lung oxygen concentration and the higher the blood oxygen level and cellular oxygen level. The higher the cellular oxygen concentration, the more damage it can perform to a cell and the harder it is for the peroxidases and superoxide-dismutases to keep the reactive species under control. Thus, more damage occurs leading, finally, to that bit of damage that can no longer be controlled.
A catch-it-all term for this is oxidative stress. All the different reactions are too numerous and too diverse to be presented here (or even on a medium as Wikipedia), but they all involve the reactive peroxides, superoxides and hydroxyl radicals $\ce{HO^.}$ (which I didn’t mention yet, but which are also terribly reactive).
Tl;dr: oxygen is great in principle, but too reactive. Cells can cope well with ambient oxygen levels and keep the reactive species under control. A rise in oxygen levels will generate too many harmful, reactive species that the cell can no longer control.
