Lost all Google Rank

This is more a Google problem than a WordPress one, but I don’t know where to ask solutions to this matter. 🙁
I made a new blog about two months ago. I was tweaking with permalink structure, and decided to keep one like this: http://mysite.com/p/%postname%.
After a few days I decided to change it to http://mysite.com/%postname% and it all worked fine.
The problem is that google indexed my whole blog while it had the /p/%postname% permalink structure, and after a few weeks, I lost my google rank and my blog went from 1600 to 90 daily google impressions because of 404 errors.

Two weeks later the number of daily impression is still the same, 70~90 per day, and even if I update my blog everyday with more and more content, it seems not to be recovering.
What should I do??