I've been with them for DEL-BOM and BOM-GOI a few times recently. No problem but they seem to like getting a few dollars (couple hundred rupees actually) for going over the weight limit far more than any other carrier I've been on in India.
Their check-in and boarding process is slower and more cumbersome than what I've experienced with the big 3/4 in India (witnessed with longer, slower moving lines often); and the staff in-flight is not as warm/friendly but still decent; the flights/seats seem more cramped; and they charge for everything, including beverages and food. The planes/seats seem clean and rather new (at least by American standards) and, although they seem to run a bit late, it's been fine enough and a truly good value.
All that said, I still prefer Jet Airways.
(Yes, Air Deccan can generally be trusted to get you from A to B without much of an issue if you give yourself enough time on either end to compensate for "normal" Indian flight issues.