The New Victoria Theatre in Newcstle-under-Lyme, Staffordshire (NB not to be confused with Newcastle-on-Tyne)puts on a fair few guitar/jazz/world orientated concerts, worth looking at their programme on their website and see if your band fits the profile at all. That is a 300 seater theatre.
For a smaller venue, very jazz orientated, the Old Brown Jug (a pub), also in Newcastle-under-Lyme, might be worth a look.