Does your symbology is part of a graphic layer or is it part of a base map?
If a basemap as a wrong symbology, then I believe it is a problem with the rest service itself. Maybe you can check the appearance of the images that are queried to the server with a tool like firebug.
Is your ArcGIS Server version 10? Using a FeatureLayer, you can only get symbology back from AGS10. I had this issue when I started using FeatureLayer's before I upgraded my server.
2. For the querying part ensure that you shape and id fields are not hidden in the map services MXD.
An ArcGIS Server 10 layer can include a Renderer in the Drawing Info.
The Flex API's FeatureLayer will use this by default. If you're using a layer that does not have any Drawing Info, then the default symbology is used. You can set a renderer or symbol on the FeatureLayer since these properties are inherited from GraphicsLayer: