The first one is definitely correct. (object of the preposition)
I'm not sure about the second one. It presents some interesting problems.
While I think it's common to use or not use the possessive of a name in this case, (a friend of Paul/Paul's), we definitely don't say "a friend of me." (a friend of mine!)