This issue I faced when I was trying to make one POC using BCS for SharePoint 2010.
First I found that my SP was trial so I upgraded it to "SharePoint Server with Enterprise Client Access License".
I was giving me same error even after upgrading then i saw on other vpc with same config and licence where it was working.
There I found the solution, which is that we need to do association of BDC service with the desired web application.
Goto : Central Admin -> Application Mgt -> Manage Web Application -> Select desired Web Application -> click 'Service Connections' from ribbon buttons -> in the popup make sure "Business Data Connectivity Service" is checked.
And bingo it worked..
