You'll need to change your IP as well. Something you have never logged in as to create the account. Sock puppet accounts can be associated by IP and social graph searches.
As for searches - I've searched a lot of random stuff totally unrelated to my personal account JUST to throw FB off while acting like a real user (liking, reading, scrolling etc.).