Do Bitcoins still need users to trust each other to feel confident? So we know that bitcoin is secure up to the point of basically proving P=NP. (Its an open question) 

So bitcoin is secure. But I feel it still suffers one problem, as with all transactions(not just bitcoin). One person must either send their stake in the barter first or receive the others and be trusted to return the payment if no escrow is involved. 

I am paraphrasing and hopefully not destroying the idea, but when I read the bitcoin whitepaper it seemed like it was aimed so that no escrow needs to be involved to transfer funds online. 

So no escrow means we all must trust one another if we want to do transactions with one another? Because one person must receive or send the goods first, and must do so on good faith that they will receive the compensation.
I will add Lohoris's comment as an answer, because it really is the answer to the question. Bitcoin does not directly try to address the issue of trust in a transaction.

Therefore, yes, some trust is needed because one party still has to be the first to hand over goods and/or cash. I just read a post on the bitcoin subreddit that relayed a story of getting ripped off after handing over BTC.

Now, Bitcoin does make some aspects that make fraud harder, most specifically a transaction log. If the recipient address is either well known, displayed on an invoice, or recorded in an email, it is trivial to prove that you sent BTC to that address. (Of course if you obfuscate the transaction through a mixer, that removes this benefit.) But, even then, that is just providing tools to law enforcement/court or some other sort of after-transaction dispute process. And, given law enforcement's lack of experience with Bitcoin, and the irreversibility of Bitcoin transactions, if you don't trust the party you are trading with then you may have to engage some sort of escrow service.

Update: Per request, this is the reddit post I mentioned.