Yes, that happens with OEM machines like Dell sometimes. But I am surprised one as late as yours has a problem with UEFI cards. Just about any modern gfx card will have a UEFI in place of an older legacy BIOS. But most will switch to legacy mode if needed. However, I too have had trouble with the R7-3xx cards in one of my machines.
I would suggest you try an Nvidia card. The machine I had problems with using the (in my case) R7-370 in, worked fine with every other card I used. Even my EVGA GTX 750 Ti and GTX 960 which also are UEFI. Unless you happen to find someone who has the exact same machine as yours and uses the same card you want to use, it will probably be a trial and error experience.
I don't know what your price range for the new card is, or what kind of performance you are after, but this MSI GTX 750 Ti has a built-in switch to change from UEFI to legacy if needed:
http://www.newegg.com/Product/Product.aspx?Item=N82E16814127783&cm_re=msi_750-_-14-127-783-_-Product