I have created a sharepoint list called "Customers" in my sample site called "contoso" and I tried to read the list as a feed using my browser. This list has four columns and Region and Size columns are Choice columns.

When I typed
http://spsrv/sites/Contoso/_vti_bin/ListData.svc/Customers
in my browser I got my customer list as a feed. Then I tried filtering for Name and it was easy and success.
http://spsrv/sites/Contoso/_vti_bin/ListData.svc/Customers?$filter=Name eq 'Fabrikam'
But when I tried to filter for Region column using
http://spsrv/sites/Contoso/_vti_bin/ListData.svc/Customers?$filter=Region eq 'East'
it did not give me the feed but gave "HTTP 400 The webpage cannot be found". I googled around but was not successful.
Then I thought a bit and and just opened the feed page viewsource. Aha! there I found the solution and what I was doing wrong. The choice columns had a suffix added as "Value". So my Region was RegionValue.

I then tried with following in my browser and successfully got the filter working against choice column.
http://spsrv/sites/Contoso/_vti_bin/ListData.svc/Customers?$filter=RegionValue eq 'East'