I know you said its not your flywheel because you just replaced it....but.....everything on my car works perfect until I decide to mess with it.
In other words, if you never had a starter problem, changed your flywheel, and all of the sudden continue to have starter problems, only one thing has changed in this equation, and thats the flywheel. Something to doublecheck you did right. Did you get the right flywheel? Is that the original engine in the car? Make sure you ordered the right flywheel weight, tooth count, and starter for the engine.
Also, if you changed your flywheel, that means you had the large shield in between the bellhousing and engine out. Make sure you put it back in. If you dont, it can throw the clearances off and cause you problems. Of course, I have seen some people run it without and do just fine, others have problems. (someone else mentioned this above I believe.)
Good luck in your search.