Heyo,
During the packaging of some gems, I got the weird error - "invalid byte sequence in US-ASCII". Since I knew US-ASCII was something related to languages, I found out pretty quickly that it was something related to the locales setting of the package. It seems the necessary locales were not getting installed in the build environment.
To solve the error
1. Add locales to Build-Depends
2. Add locales-all to Build-Conflicts as locales-all doesn't provide the stuff given by locales package. So, it should be prevented from being installed by default. Refer this bug report
3. Locales should be defined in some location in the build environment. That path should be given as an environment variable while building
3.1 It requires the default build method to be overriden
3.2 It required the clean method to be overriden
3.3 Both of this is done by modifying the debian/rules file

This is the modified debian/rules file
################### MODIFIED DEBIAN/RULES FILE BEGINS #################################
#!/usr/bin/make -f
%:
     mkdir -p debian/build/locale
     localedef -f UTF-8 -i en_US debian/build/locale/en_US.UTF-8
     LOCPATH=$(CURDIR)/debian/build/locale LC_ALL=en_US.UTF-8 dh $@ --buildsystem=ruby --with ruby


override_dh_clean:
     LOCPATH=$(CURDIR)/debian/build/locale LC_ALL=en_US.UTF-8 dh_clean --buildsystem=ruby
     rm -rf debian/build/
################### MODIFIED DEBIAN/RULES FILE ENDS #################################

Let's analyse the code
1. In the % block, we are overriding the default build statement. We first create a temporary location for defining the locales. In the next statement, we define necessary locales. Then the path and LC_ALL environment variable is set while running the dh $@ statement.
2. In the clean block, we must call the dh_clean statement with both environment variables set, just like dh $@ statement. Also, we must remove the temporary directory we created.

Hope this helps someone who gets stuck at the issue.