Was there truly no magic in Sword Art Online? In the first episode, when Kirito was showing Klein the ropes of combat, the conversation goes

Kirito: However, there is no magic.
Klein: An RPG without magic? That is a bold decision.

However later on in the show, Kirito visits Lizbeth's shop in Temperature of the Heart.. Kirito is in shop for another sword, and shows Lizbeth his Elucidator.
Lizbeth responds with:

An Elucidator! This is the gnarliest magic sword a person can get from a monster drop.

If magic did not exist, how would there be a magic sword?
In SAO, there are no magical spells that players can cast. However, according to the light novel, SAO does have some magical items and aspects. Some of these items include gems which players could use to instantly teleport, heal or recover from poison. There is also the Divine Stone of Returning Soul that revives a fallen player.



This text and the following quotes are taken from the second volume of the light novel.


  The few magic items in this world where  had been excluded were all shaped like gems. Blue was for instant teleportation, pink for recovering HP, green for antidotes, and so on. They were all convenient items that produced instant effects, but they were also expensive. So in most cases people used cheaper items such as slow-acting potions after running away from a fight


Certain parts of the game could also be considered magical such as the teleportation gates used to move between floors, and the alters found in churches. These altars would allow a player to bless their weapons when facing undead opponents. Also, if a player was cursed they could use the altar to remove the debuff.


  It was the unmistakable mark of a church, of which at least one exists in every town. And through the altar inside, tasks such as removing the attack unique to monsters, «Curse», and the blessing of weapons to go up against undead monsters with, were possible. In SAO, where magic-based components barely exist, it could be considered a most mysterious place.


As for Elucidator, the light novel describes this as a demon sword, not a magic sword. However, both the English sub and dub refer to it as a magic sword. As discussed in the comments, I believe this is an error in translation. So there are no magical weapons in SAO, but they do seem to have other forms of magic.




  One is «Player made», which meant weapons made by us blacksmiths. The other included weapons that one gained from adventuring as «Monster drops». Needless to say, blacksmiths don't like drop weapons all that much. I couldn't even begin to count all the names like 'Unnamed' or 'No brand' that were given to them.
  But this sword seemed to be a very rare item amongst monster drops. If you compared the average quality of player-made weapons and monster drops, the former was better. But once in a while, «Demon Swords» such as this one appeared— that was what I heard.