Not necessarily - we know that the elves lost both their immortality and their magic around the fall of Arlathan. The fall came at around the same time the elven gods were sealed away.
That we actually don't know - we have no idea how much time has passed between the sealing of elvhen gods and the fall of Arlathan.
Finally, Solas implies in party banter with Dorian that physically visiting the fade was not impossible for elves in ancient times
... Actually, he says the exact opposite
He responds to Dorian marveling that the Fade was visited the second time in history, by responding to it "In human history", which itself leaves a heavy implication that elves visiting the Fade physically was the thing that happened. In fact, we have a pretty large amount of broken eluvians in the Fade itself as well as constructs as Crossroads that suggest elves could cross and shape the Fade relatively easily.
(...) the veil was somehow different in nature back then.
I agree that the Veil might have had a different nature - probably one that was more fluid. Though how and when its nature changed is anyone's guess.
As for Fade being blighted - well, the Fade reflects the world of the living, so the fact that it looks blighted might be the result of the world still carrying the scars of it. Still, the Fade itself might have changed over time, and not for anything better.
After all, after Solas and Cole enter the Fade in Adamant, Cole is bewildered and tells Solas that the Fade is not how it should be (I assume however it's partially because he's found himself in the realm governed by Nightmare, which wasn't the part of the Fade he was familiar with to begin with) and Solas response to it was: "It's alright... We'll make it right". Hmmmmmmm.... 
The loss of elven magic and the loss of elven immortality could both be attributed to whatever the hell it was that Solas actually did when he rebelled; perhaps it was changing the nature of the veil to trap the gods (resulting in the loss of the elves innate connection to the fade,) or perhaps messing with the abyss to seal the Forgotten Ones. (I can't be alone in thinking that if the blight came from anywhere, something called 'the abyss' seems pretty danm suspicious.)
True, though that leaves open the question as to how Fen'Harel could freely travel between both realms - apparently without fear, or maybe even negative effect on him. It might be that the Blight might be some powerful magic gone wrong, maybe twisted due to some sort of cataclysmic event I'm not really sure Solas can be blamed for.
The loss of both these things at the same time doesn't mean that their magic caused immortality. Rather, it implies that whatever broke the world and caused the blight broke it substantially worse than anyone previously realised.
Yet, broke it to a point where both magic and immortality of elves were gone, meaning that both were linked in some way.